LeetCode:字符串的前缀分数和

LeetCode:字符串的前缀分数和

题目内容

给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。

定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。

例如，如果 words = [“a”, “ab”, “abc”, “cab”] ，那么 “ab” 的分数是 2 ，因为 “ab” 是 “ab” 和 “abc” 的一个前缀。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。

注意：字符串视作它自身的一个前缀。

示例 1：

输入：words = [“abc”,“ab”,“bc”,“b”]
输出：[5,4,3,2]
解释：对应每个字符串的答案如下：

• “abc” 有 3 个前缀：“a”、“ab” 和 “abc” 。
• 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” ，1 个字符串的前缀为 “abc” 。
  总计 answer[0] = 2 + 2 + 1 = 5 。
• “ab” 有 2 个前缀：“a” 和 “ab” 。
• 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” 。
  总计 answer[1] = 2 + 2 = 4 。
• “bc” 有 2 个前缀：“b” 和 “bc” 。
• 2 个字符串的前缀为 “b” ，1 个字符串的前缀为 “bc” 。
  总计 answer[2] = 2 + 1 = 3 。
• “b” 有 1 个前缀：“b”。
• 2 个字符串的前缀为 “b” 。
  总计 answer[3] = 2 。
  示例 2：

输入：words = [“abcd”]
输出：[4]
解释：
“abcd” 有 4 个前缀 “a”、“ab”、“abc” 和 “abcd”。
每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 由小写英文字母组成

解题思路

先读懂题目，题目的意思是对于其中的某个单词以示例1为例，对于word = [ "abc","ab","bc","b"]中的abc而言，需要将其进行拆分成a,ab,abc对于这些子串一个去word里面看是不是某个单词的前缀。

其中a是abc和ab的前缀,ab是ab和abc的前缀，abc是abc的前缀。

如果使用暴力算法的话就是这样去遍历所有的单词，计算每个单词的前缀和。。。。但是这样会超时。

所以使用字典树，进行解题。

字典树是一个为了解决单词匹配类型题目而设计的数据结构。每个节点下面有26个对应子节点，对应26个字母。

我们继续以word = [ "abc","ab","bc","b"]为例，对于abc而言，它在字典树的存储模式如下图所示。

当字典树只有abc时，它的前缀和为a+ab+abc = 1+1+1。。当字典树中加入ab时，abc的前缀和为a+ab+abc = 2+2+1。。。。当插入新的单词时经历过哪个节点，那个节点对应的前缀数目就会+1。。。。

所以只需要在字典树的每个节点上设立一个value值，当插入新单词时，经历哪个节点就在那个节点上的value上++

而要得到某个单词的前缀和，只需要经历哪个节点就把那个节点的value进行累加，然后获取最终结果。

代码实现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct TrieNode {
  vector<TrieNode*> child;
  int value;
  TrieNode() {
    this->child = vector<TrieNode*>(26, nullptr);
    this->value = 0;
  }
};
void insert(TrieNode* root, const string& word) {  //插入单词
  TrieNode* node = root;
  for (int i = 0; i < word.size(); i++) {
    if (node->child[word[i] - 'a'] == nullptr) {
      node->child[word[i] - 'a'] = new TrieNode();
    }
    node = node->child[word[i] - 'a'];
    node->value++;
  }
}
class WordDictionary {
 public:
  WordDictionary() { trie = new TrieNode(); }
  void addWord(string word) { insert(trie, word); }
  int search(string word) {
    int sum = 0;
    dfs(word, 0, sum, trie);
    return sum;
  }
  void dfs(const string& word, int index, int& sum, TrieNode* node) {
    if (index == word.size()) {
      return;
    }
    char ch = word[index];
    if (ch >= 'a' && ch <= 'z') {
      TrieNode* child = node->child[ch - 'a'];
      if (child != nullptr) {
        sum += child->value;  //累加value值
        dfs(word, index + 1, sum, child);
      }
    }
  }

 private:
  TrieNode* trie;
};
int main() {
  WordDictionary a;
  a.addWord("abc");
  a.addWord("ab");
  a.addWord("bc");
  a.addWord("b");
  cout << a.search("abc") << endl;
  cout << a.search("ab") << endl;
  cout << a.search("bc") << endl;
  cout << a.search("b") << endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

运行截图