class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
}
};
2416. 字符串的前缀分数和
给你一个长度为 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 <= 10001 <= words[i].length <= 1000words[i] 由小写英文字母组成原站题解
python3 解法, 执行用时: 7312 ms, 内存消耗: 478.7 MB, 提交时间: 2022-10-19 14:53:58
class Trie:
def __init__(self):
self.child = [None for _ in range(26)]
self.cnt = 0
def insert(self, word: str) -> None:
rt = self
for c in word:
ID = ord(c) - ord('a')
if rt.child[ID] == None:
rt.child[ID] = Trie()
rt = rt.child[ID]
rt.cnt += 1
def qeury(self, prefix: str) -> int:
rt = self
res = 0
for c in prefix:
ID = ord(c)- ord('a')
if rt.child[ID] == None:
break
rt = rt.child[ID]
res += rt.cnt
return res
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
n = len(words)
T = Trie()
for word in words:
T.insert(word)
res = [0 for _ in range(n)]
for i, word in enumerate(words):
res[i] = T.qeury(word)
return res
python3 解法, 执行用时: 2352 ms, 内存消耗: 265.4 MB, 提交时间: 2022-10-19 14:53:10
Trie = lambda : defaultdict(Trie)
CNT = '#'
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
tr = Trie()
for w in words:
cur = tr
for ch in w:
cur = cur[ch]
cur[CNT] = cur.get(CNT, 0) + 1
res = []
for w in words:
cur, ans = tr, 0
for ch in w:
cur = cur[ch]
ans += cur[CNT]
res.append(ans)
return res
python3 解法, 执行用时: 7124 ms, 内存消耗: 590.2 MB, 提交时间: 2022-10-19 14:51:13
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
cnt = Counter(w[:i+1] for w in words for i in range(len(w)))
return [sum(cnt[w[:i+1]] for i in range(len(w))) for w in words]