diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-09-24 21:27:56 -0600 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-09-24 21:27:56 -0600 |
commit | c53c788fc24031c6185ebdd8f723895ee2c000da (patch) | |
tree | 9e345315f9fda85185585b2f936ca428b4c1e152 /sum_prefix_score_string.py | |
parent | 97fb1a16a79fea703c4abb77c0fef85b8827a37d (diff) | |
download | leetcode-c53c788fc24031c6185ebdd8f723895ee2c000da.tar.gz leetcode-c53c788fc24031c6185ebdd8f723895ee2c000da.zip |
2416. sum of prefix scores of strings
Diffstat (limited to 'sum_prefix_score_string.py')
-rw-r--r-- | sum_prefix_score_string.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/sum_prefix_score_string.py b/sum_prefix_score_string.py new file mode 100644 index 0000000..8c0b4ab --- /dev/null +++ b/sum_prefix_score_string.py @@ -0,0 +1,46 @@ +# 2416. Sum of Prefix Scores of Strings + +""" +you are given an array 'words' of size 'n' consisting of non empty strings. +we define the score of a string 'word' as the number of strings 'words[i]' +such that 'word' is a prefix of 'words[i]'. return an array 'answer' of size +'n' where 'answer[i]' is the sum of the scores of every non empty prefix of +'words[i]'. note that a string is considered as a prefix of itself. +""" + + +class Trie: + def __init__(self): + self.children = [None] * 26 + self.cnt = 0 + + +class Solution(object): + def sumPrefixScores(self, words): + """ + :type words: List[str] + :rtype: List[int] + """ + trie, a, ans = Trie(), ord("a"), [] + for w in words: + t = trie + for c in w: + c = ord(c) - a + if not t.children[c]: + t.children = Trie() + t.children[c].cnt += 1 + t = t.children[c] + for w in words: + t, curr = trie, 0 + for c in w: + c = ord(c) - a + curr += t.children[c].cnt + t = t.children[c] + ans.append(curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.sumPrefixScores(words=["abc", "ab", "bc", "b"])) + print(obj.sumPrefixScores(words=["abcd"])) |