2416. Sum of Prefix Scores of Strings
## 思路
跟前幾天一樣是TrieTree
把Word加進Trie時 每個prefix的count都+1
最後再掃Trie得到prefix score總和
## Code
```python
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
class TrieTree:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for ch in word:
if ch not in curr.children:
curr.children[ch] = TrieNode()
curr = curr.children[ch]
curr.count += 1
def search(self, word):
res = 0
curr = self.root
for ch in word:
curr = curr.children[ch]
res += curr.count
return res
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
trie = TrieTree()
for word in words:
trie.insert(word)
return [trie.search(word) for word in words]
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727230177.A.CA4.html