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" is 2, 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.

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));
    };
    
    

All Problems

All Solutions