Leetcode Weekly Contest 311 Q4

Posted on

Original Problem: https://leetcode.com/contest/weekly-contest-311/problems/sum-of-prefix-scores-of-strings/

For a string , we need to find all its prefixes and all strings with the same prefix. We can achieve this goal by using a trie tree with a meta tag in each node to record the time for a specific prefix to happen in all strings.

Time complexity: Space complexity:

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        tree = {}
        # build tree
        for word in words:
            cur = tree
            for i in word:
                if cur.get(i):
                    cur = cur[i]
                    cur['meta'] += 1
                else:
                    cur[i] = {}
                    cur = cur[i]
                    cur['meta'] = 1
        
        # calculate
        ans = []
        for word in words:
            t = 0
            cur = tree
            for i in word:
                cur = cur[i]
                t += cur['meta']
            ans.append(t)
        
        return ans