aboutsummaryrefslogtreecommitdiff
path: root/sum_prefix_score_string.py
diff options
context:
space:
mode:
authorJack Sangdahl <jack@pngu.org>2024-09-24 21:27:56 -0600
committerJack Sangdahl <jack@pngu.org>2024-09-24 21:27:56 -0600
commitc53c788fc24031c6185ebdd8f723895ee2c000da (patch)
tree9e345315f9fda85185585b2f936ca428b4c1e152 /sum_prefix_score_string.py
parent97fb1a16a79fea703c4abb77c0fef85b8827a37d (diff)
downloadleetcode-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.py46
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"]))