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

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

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

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class TrieNode {
  4. public:
  5. bool isWord = false;
  6. int counter = 0;
  7. TrieNode* children[26]{};
  8. TrieNode() = default;
  9. };
  10. void buildTrie(TrieNode* root, string& w) {
  11. TrieNode* curr=root;
  12. for(char& ch: w) {
  13. if(!curr->children[ch-'a']) curr->children[ch-'a']=new TrieNode();
  14. curr=curr->children[ch-'a'];
  15. curr->counter++;
  16. }
  17. curr->isWord=true;
  18. }
  19. long long check(TrieNode* root, string& w) {
  20. TrieNode* curr=root;
  21. long long res=0ll;
  22. for(int i=0; i<w.size(); i++) {
  23. char ch=w[i];
  24. curr=curr->children[ch-'a'];
  25. if(curr->isWord) res++;
  26. }
  27. return res;
  28. }
  29. long long countPairs(vector<string> words) {
  30. TrieNode* root=new TrieNode();
  31. for(auto& w: words) {
  32. buildTrie(root, w);
  33. }
  34. long long res=0ll;
  35. for(auto w: words) {
  36. res+=check(root, w);
  37. }
  38. return res;
  39. }
  40. int main() {
  41. vector<string> v={"abc","a","a","b","ab","ac"};
  42. cout<<countPairs(v)<<"\n";
  43. return 0;
  44. }

不幸的是,它返回的结果是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.写下你的代码做了什么。然后仔细地一步一步地调试,并将它与你写下的内容进行比较。

相关问题