Skip to content

Commit e14fade

Browse files
yanglbmeyanglbme
authored
feat: update solutions to lc problem: No.2416 (doocs#3348)
No.2416.Sum of Prefix Scores of Strings
1 parent fffbcb0 commit e14fade

6 files changed

Lines changed: 104 additions & 183 deletions

File tree

‎solution/2400-2499/2416.Sum of Prefix Scores of Strings/README.md‎

Lines changed: 27 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,7 @@ tags:
4747
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。
4848
总计 answer[1] = 2 + 2 = 4 。
4949
- "bc" 有 2 个前缀："b" 和 "bc" 。
50-
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。
50+
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。
5151
总计 answer[2] = 2 + 1 = 3 。
5252
- "b" 有 1 个前缀："b"。
5353
- 2 个字符串的前缀为 "b" 。
@@ -81,26 +81,38 @@ tags:
8181

8282
### 方法一：前缀树
8383

84-
用前缀树维护所有字符串的前缀以及每个前缀出现的次数。
84+
我们可以用前缀树来维护所有字符串的前缀以及每个前缀出现的次数。
8585

86-
然后遍历每个字符串，累加每个前缀的出现次数即可。
86+
定义前缀树节点结构体 `Trie`，包含两个属性：
8787

88-
时间复杂度 $O(n \times m)$。其中 $n$, $m$ 分别为字符串数组 `words` 的长度和其中字符串的最大长度。
88+
- `children`：长度为 26 的数组，用于存储当前节点的子节点。
89+
- `cnt`：当前节点的出现次数。
90+
91+
定义前缀树的两个方法：
92+
93+
- `insert`：插入一个字符串，将其前缀插入前缀树。
94+
- `search`：搜索一个字符串，返回其前缀的出现次数。
95+
96+
我们遍历所有字符串，将每个字符串插入前缀树中。然后再遍历所有字符串，对每个字符串调用 `search` 方法，累加每个前缀的出现次数即可。
97+
98+
时间复杂度 $O(L)$，空间复杂度 $O(L)$，其中 $L$ 是所有字符串的总长度。
8999

90100
<!-- tabs:start -->
91101

92102
#### Python3
93103

94104
```python
95105
class Trie:
106+
__slots__ = "children", "cnt"
107+
96108
def __init__(self):
97109
self.children = [None] * 26
98110
self.cnt = 0
99111

100112
def insert(self, w):
101113
node = self
102114
for c in w:
103-
idx = ord(c) - ord('a')
115+
idx = ord(c) - ord("a")
104116
if node.children[idx] is None:
105117
node.children[idx] = Trie()
106118
node = node.children[idx]
@@ -110,7 +122,7 @@ class Trie:
110122
node = self
111123
ans = 0
112124
for c in w:
113-
idx = ord(c) - ord('a')
125+
idx = ord(c) - ord("a")
114126
if node.children[idx] is None:
115127
return ans
116128
node = node.children[idx]
@@ -180,19 +192,17 @@ class Solution {
180192
```cpp
181193
class Trie {
182194
private:
183-
vector<Trie*> children;
184-
int cnt;
195+
Trie* children[26]{};
196+
int cnt = 0;
185197

186198
public:
187-
Trie()
188-
: children(26)
189-
, cnt(0) {}
190-
191199
void insert(string& w) {
192200
Trie* node = this;
193201
for (char c : w) {
194202
int idx = c - 'a';
195-
if (!node->children[idx]) node->children[idx] = new Trie();
203+
if (!node->children[idx]) {
204+
node->children[idx] = new Trie();
205+
}
196206
node = node->children[idx];
197207
++node->cnt;
198208
}
@@ -203,7 +213,9 @@ public:
203213
int ans = 0;
204214
for (char c : w) {
205215
int idx = c - 'a';
206-
if (!node->children[idx]) return ans;
216+
if (!node->children[idx]) {
217+
return ans;
218+
}
207219
node = node->children[idx];
208220
ans += node->cnt;
209221
}
@@ -279,42 +291,6 @@ func sumPrefixScores(words []string) []int {
279291

280292
#### TypeScript
281293

282-
```ts
283-
function sumPrefixScores(words: string[]): number[] {
284-
const map = new Map();
285-
286-
for (const word of words) {
287-
const n = word.length;
288-
for (let i = 1; i <= n; i++) {
289-
const s = word.slice(0, i);
290-
map.set(s, (map.get(s) ?? 0) + 1);
291-
}
292-
}
293-
294-
return words.map(word => {
295-
const n = word.length;
296-
let count = 0;
297-
for (let i = 1; i <= n; i++) {
298-
const s = word.slice(0, i);
299-
count += map.get(s);
300-
}
301-
return count;
302-
});
303-
}
304-
```
305-
306-
<!-- tabs:end -->
307-
308-
<!-- solution:end -->
309-
310-
<!-- solution:start -->
311-
312-
### 方法二
313-
314-
<!-- tabs:start -->
315-
316-
#### TypeScript
317-
318294
```ts
319295
class Trie {
320296
children: Array<any>;
@@ -357,11 +333,7 @@ function sumPrefixScores(words: string[]): number[] {
357333
for (const w of words) {
358334
trie.insert(w);
359335
}
360-
let ans = [];
361-
for (const w of words) {
362-
ans.push(trie.search(w));
363-
}
364-
return ans;
336+
return words.map(w => trie.search(w));
365337
}
366338
```
367339

‎solution/2400-2499/2416.Sum of Prefix Scores of Strings/README_EN.md‎

Lines changed: 27 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -79,28 +79,40 @@ Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
7979

8080
<!-- solution:start -->
8181

82-
### Solution 1: Trie
82+
### Solution 1: Prefix Tree
8383

84-
Use a trie to maintain the prefixes of all strings and the occurrence count of each prefix.
84+
We can use a prefix tree to maintain all prefixes of the strings and count the occurrences of each prefix.
8585

86-
Then, traverse each string, accumulating the occurrence count of each prefix.
86+
Define the prefix tree node structure `Trie`, which includes two properties:
8787

88-
The time complexity is $O(n \times m)$. Here, $n$ and $m$ are the length of the string array `words` and the maximum length of the strings in it, respectively.
88+
- `children`: An array of length 26 used to store the current node's children.
89+
- `cnt`: The occurrence count of the current node.
90+
91+
Define two methods for the prefix tree:
92+
93+
- `insert`: Inserts a string, adding its prefixes into the prefix tree.
94+
- `search`: Searches for a string and returns the occurrence count of its prefixes.
95+
96+
We traverse all strings, inserting each string into the prefix tree. Then we traverse all strings again, calling the `search` method for each string and summing up the occurrence counts of each prefix.
97+
98+
Time complexity is $O(L)$, and space complexity is $O(L)$, where $L$ is the total length of all strings.
8999

90100
<!-- tabs:start -->
91101

92102
#### Python3
93103

94104
```python
95105
class Trie:
106+
__slots__ = "children", "cnt"
107+
96108
def __init__(self):
97109
self.children = [None] * 26
98110
self.cnt = 0
99111

100112
def insert(self, w):
101113
node = self
102114
for c in w:
103-
idx = ord(c) - ord('a')
115+
idx = ord(c) - ord("a")
104116
if node.children[idx] is None:
105117
node.children[idx] = Trie()
106118
node = node.children[idx]
@@ -110,7 +122,7 @@ class Trie:
110122
node = self
111123
ans = 0
112124
for c in w:
113-
idx = ord(c) - ord('a')
125+
idx = ord(c) - ord("a")
114126
if node.children[idx] is None:
115127
return ans
116128
node = node.children[idx]
@@ -180,19 +192,17 @@ class Solution {
180192
```cpp
181193
class Trie {
182194
private:
183-
vector<Trie*> children;
184-
int cnt;
195+
Trie* children[26]{};
196+
int cnt = 0;
185197

186198
public:
187-
Trie()
188-
: children(26)
189-
, cnt(0) {}
190-
191199
void insert(string& w) {
192200
Trie* node = this;
193201
for (char c : w) {
194202
int idx = c - 'a';
195-
if (!node->children[idx]) node->children[idx] = new Trie();
203+
if (!node->children[idx]) {
204+
node->children[idx] = new Trie();
205+
}
196206
node = node->children[idx];
197207
++node->cnt;
198208
}
@@ -203,7 +213,9 @@ public:
203213
int ans = 0;
204214
for (char c : w) {
205215
int idx = c - 'a';
206-
if (!node->children[idx]) return ans;
216+
if (!node->children[idx]) {
217+
return ans;
218+
}
207219
node = node->children[idx];
208220
ans += node->cnt;
209221
}
@@ -279,42 +291,6 @@ func sumPrefixScores(words []string) []int {
279291

280292
#### TypeScript
281293

282-
```ts
283-
function sumPrefixScores(words: string[]): number[] {
284-
const map = new Map();
285-
286-
for (const word of words) {
287-
const n = word.length;
288-
for (let i = 1; i <= n; i++) {
289-
const s = word.slice(0, i);
290-
map.set(s, (map.get(s) ?? 0) + 1);
291-
}
292-
}
293-
294-
return words.map(word => {
295-
const n = word.length;
296-
let count = 0;
297-
for (let i = 1; i <= n; i++) {
298-
const s = word.slice(0, i);
299-
count += map.get(s);
300-
}
301-
return count;
302-
});
303-
}
304-
```
305-
306-
<!-- tabs:end -->
307-
308-
<!-- solution:end -->
309-
310-
<!-- solution:start -->
311-
312-
### Solution 2
313-
314-
<!-- tabs:start -->
315-
316-
#### TypeScript
317-
318294
```ts
319295
class Trie {
320296
children: Array<any>;
@@ -357,11 +333,7 @@ function sumPrefixScores(words: string[]): number[] {
357333
for (const w of words) {
358334
trie.insert(w);
359335
}
360-
let ans = [];
361-
for (const w of words) {
362-
ans.push(trie.search(w));
363-
}
364-
return ans;
336+
return words.map(w => trie.search(w));
365337
}
366338
```
367339

‎solution/2400-2499/2416.Sum of Prefix Scores of Strings/Solution.cpp‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,16 @@
11
class Trie {
22
private:
3-
vector<Trie*> children;
4-
int cnt;
3+
Trie* children[26]{};
4+
int cnt = 0;
55

66
public:
7-
Trie()
8-
: children(26)
9-
, cnt(0) {}
10-
117
void insert(string& w) {
128
Trie* node = this;
139
for (char c : w) {
1410
int idx = c - 'a';
15-
if (!node->children[idx]) node->children[idx] = new Trie();
11+
if (!node->children[idx]) {
12+
node->children[idx] = new Trie();
13+
}
1614
node = node->children[idx];
1715
++node->cnt;
1816
}
@@ -23,7 +21,9 @@ class Trie {
2321
int ans = 0;
2422
for (char c : w) {
2523
int idx = c - 'a';
26-
if (!node->children[idx]) return ans;
24+
if (!node->children[idx]) {
25+
return ans;
26+
}
2727
node = node->children[idx];
2828
ans += node->cnt;
2929
}
@@ -44,4 +44,4 @@ class Solution {
4444
}
4545
return ans;
4646
}
47-
};
47+
};

‎solution/2400-2499/2416.Sum of Prefix Scores of Strings/Solution.py‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,14 @@
11
class Trie:
2+
__slots__ = "children", "cnt"
3+
24
def __init__(self):
35
self.children = [None] * 26
46
self.cnt = 0
57

68
def insert(self, w):
79
node = self
810
for c in w:
9-
idx = ord(c) - ord('a')
11+
idx = ord(c) - ord("a")
1012
if node.children[idx] is None:
1113
node.children[idx] = Trie()
1214
node = node.children[idx]
@@ -16,7 +18,7 @@ def search(self, w):
1618
node = self
1719
ans = 0
1820
for c in w:
19-
idx = ord(c) - ord('a')
21+
idx = ord(c) - ord("a")
2022
if node.children[idx] is None:
2123
return ans
2224
node = node.children[idx]

0 commit comments

Comments
 (0)