Welcome to Subscribe On Youtube
2416. Sum of Prefix Scores of Strings
Description
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 <= 10001 <= words[i].length <= 1000words[i]consists of lowercase English letters.
Solutions
Solution 1: Trie
Use a trie to maintain the prefixes of all strings and the occurrence count of each prefix.
Then, traverse each string, accumulating the occurrence count of each prefix.
The time complexity is $O(n \times m)$. Here, $n$ and $m$ are the length of the string array words and the maximum length of the strings in it, respectively.
-
class Trie { private Trie[] children = new Trie[26]; private int cnt; public void insert(String w) { Trie node = this; for (char c : w.toCharArray()) { c -= 'a'; if (node.children[c] == null) { node.children[c] = new Trie(); } node = node.children[c]; ++node.cnt; } } public int search(String w) { Trie node = this; int ans = 0; for (char c : w.toCharArray()) { c -= 'a'; if (node.children[c] == null) { return ans; } node = node.children[c]; ans += node.cnt; } return ans; } } class Solution { public int[] sumPrefixScores(String[] words) { Trie trie = new Trie(); for (String w : words) { trie.insert(w); } int[] ans = new int[words.length]; for (int i = 0; i < words.length; ++i) { ans[i] = trie.search(words[i]); } return ans; } } -
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; } }; -
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] -
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 } -
function sumPrefixScores(words: string[]): number[] { const map = new Map(); for (const word of words) { const n = word.length; for (let i = 1; i <= n; i++) { const s = word.slice(0, i); map.set(s, (map.get(s) ?? 0) + 1); } } return words.map(word => { const n = word.length; let count = 0; for (let i = 1; i <= n; i++) { const s = word.slice(0, i); count += map.get(s); } return count; }); } -
class Trie { constructor() { this.children = {}; this.cnt = 0; } insert(w) { let node = this; for (const c of w) { if (!node.children[c]) { node.children[c] = new Trie(); } node = node.children[c]; node.cnt++; } } search(w) { let node = this; let ans = 0; for (const c of w) { if (!node.children[c]) { return ans; } node = node.children[c]; ans += node.cnt; } return ans; } } /** * @param {string[]} words * @return {number[]} */ var sumPrefixScores = function (words) { const trie = new Trie(); for (const w of words) { trie.insert(w); } return words.map(w => trie.search(w)); };