Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2416.html
2416. Sum of Prefix Scores of Strings
- Difficulty: Hard.
- Related Topics: .
- Similar Questions: Design Add and Search Words Data Structure, Maximum XOR of Two Numbers in an Array, Map Sum Pairs.
Problem
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]
.
- For example, if
words = ["a", "ab", "abc", "cab"]
, then the score of"ab"
is2
, since"ab"
is a prefix of both"ab"
and"abc"
.
Return an array **answer
of size n
where answer[i]
is the sum of scores of every non-empty prefix of **words[i]
.
Note that a string is considered as a prefix of itself.
Example 1:
Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.
Example 2:
Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
Constraints:
-
1 <= words.length <= 1000
-
1 <= words[i].length <= 1000
-
words[i]
consists of lowercase English letters.
Solution (Java, C++, Python)
-
class Trie { Trie[] ch = new Trie[26]; int visited = 0; } class Solution { public int[] sumPrefixScores(String[] words) { Trie trie = new Trie(); int[] ans = new int[words.length]; int k = 0; for (String x: words) { Trie t = trie; for (int i = 0; i < x.length(); i++) { int c = x.charAt(i) - 'a'; if (t.ch[c] == null) t.ch[c] = new Trie(); t.ch[c].visited++; t = t.ch[c]; } } for (String x: words) { Trie t = trie; int curr = 0; for (int i = 0; i < x.length(); i++) { int c = x.charAt(i) - 'a'; curr += t.ch[c].visited; t = t.ch[c]; } ans[k++] = curr; } return ans; } }
-
class Trie: def __init__(self): self.children = [None] * 26 self.cnt = 0 def insert(self, w): node = self for c in w: idx = ord(c) - ord('a') if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.cnt += 1 def search(self, w): node = self ans = 0 for c in w: idx = ord(c) - ord('a') if node.children[idx] is None: return ans node = node.children[idx] ans += node.cnt return ans class Solution: def sumPrefixScores(self, words: List[str]) -> List[int]: trie = Trie() for w in words: trie.insert(w) return [trie.search(w) for w in words] ############ # 2416. Sum of Prefix Scores of Strings # https://leetcode.com/problems/sum-of-prefix-scores-of-strings class Solution: def sumPrefixScores(self, words: List[str]) -> List[int]: N = len(words) res = [0] * N mp = defaultdict(int) for word in words: prefix = "" for char in word: prefix += char mp[prefix] += 1 for index, word in enumerate(words): prefix = "" count = 0 for char in word: prefix += char count += mp[prefix] res[index] = count return res
-
class Trie { private: vector<Trie*> children; int cnt; public: Trie() : children(26) , cnt(0) {} void insert(string& w) { Trie* node = this; for (char c : w) { int idx = c - 'a'; if (!node->children[idx]) node->children[idx] = new Trie(); node = node->children[idx]; ++node->cnt; } } int search(string& w) { Trie* node = this; int ans = 0; for (char c : w) { int idx = c - 'a'; if (!node->children[idx]) return ans; node = node->children[idx]; ans += node->cnt; } return ans; } }; class Solution { public: vector<int> sumPrefixScores(vector<string>& words) { Trie* trie = new Trie(); for (auto& w : words) { trie->insert(w); } vector<int> ans; for (auto& w : words) { ans.push_back(trie->search(w)); } return ans; } };
-
type Trie struct { children [26]*Trie cnt int } func newTrie() *Trie { return &Trie{} } func (this *Trie) insert(w string) { node := this for _, c := range w { c -= 'a' if node.children[c] == nil { node.children[c] = newTrie() } node = node.children[c] node.cnt++ } } func (this *Trie) search(word string) int { node := this ans := 0 for _, c := range word { c -= 'a' if node.children[c] == nil { return ans } node = node.children[c] ans += node.cnt } return ans } func sumPrefixScores(words []string) []int { trie := newTrie() for _, w := range words { trie.insert(w) } ans := make([]int, len(words)) for i, w := range words { ans[i] = trie.search(w) } return ans }
-
class Trie { children: Array<any>; cnt: number; constructor() { this.children = Array(26); this.cnt = 0; } insert(w: string): void { let node = this; for (const c of w) { const idx = c.charCodeAt(0) - 'a'.charCodeAt(0); if (!node.children[idx]) { node.children[idx] = new Trie(); } node = node.children[idx]; node.cnt++; } } search(w: string): number { let node = this; let ans = 0; for (const c of w) { const idx = c.charCodeAt(0) - 'a'.charCodeAt(0); if (!node.children[idx]) { return ans; } node = node.children[idx]; ans += node.cnt; } return ans; } } function sumPrefixScores(words: string[]): number[] { const trie = new Trie(); for (const w of words) { trie.insert(w); } let ans = []; for (const w of words) { ans.push(trie.search(w)); } return ans; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).