c++ 查找重复单词或其他单词的前缀的数量

xzlaal3s  于 2022-12-01  发布在  其他
关注(0)|答案(1)|浏览(161)

我们有一个长度为words的数组,最大长度为105,每个单词的长度不超过10。我们想计算两个单词相等或一个是另一个的前缀的对的数量。例如,对于words = ["abc","a","a","b","ab","ac"],预期输出应为8
我认为这应该用一个trie来解决:

#include <bits/stdc++.h>
using namespace std;
 
class TrieNode {
public:
    bool isWord = false;
    int counter = 0;
    TrieNode* children[26]{};
 
    TrieNode() = default;
};
 
void buildTrie(TrieNode* root, string& w) {
    TrieNode* curr=root;
    for(char& ch: w) {
        if(!curr->children[ch-'a']) curr->children[ch-'a']=new TrieNode();
        curr=curr->children[ch-'a'];
        curr->counter++;
    }
    curr->isWord=true;
}
 
long long check(TrieNode* root, string& w) {
    TrieNode* curr=root;
 
    long long res=0ll;
    for(int i=0; i<w.size(); i++) {
        char ch=w[i];
        curr=curr->children[ch-'a'];
        if(curr->isWord) res++;
    }
 
    return res;
}
 
long long countPairs(vector<string> words) {
    TrieNode* root=new TrieNode();
    for(auto& w: words) {
        buildTrie(root, w);
    }
 
    long long res=0ll;
    for(auto w: words) {
        res+=check(root, w);
    }
 
    return res;
}
 
 
int main() {
    vector<string> v={"abc","a","a","b","ab","ac"};
    cout<<countPairs(v)<<"\n";
 
    return 0;
}

不幸的是,它返回的结果是10,而不是8(ideone链接here)。我认为不正确的是处理重复项(aa)的方式。
如何纠正?

jogvjijk

jogvjijk1#

首先是:应该避免#include <bits/stdc++.h>using namespace std;。这是不好的做法。
基本上,得到的结果是向量中的字符数,将所有的单词填入Trie数据结构,然后在check函数中再次遍历单词,每次单词的子串停在isWord = true节点时,加+1,同时将"abc""abc"进行比较,重复项不计算在内。
所以你需要做的是:
1.请确保不将同一索引与其自身进行比较。
1.计算重复项。在TrieNode类中有变量counter。我认为它可以帮助您。
1.写下你的代码做了什么。然后仔细地一步一步地调试,并将它与你写下的内容进行比较。

相关问题