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.\
어제 풀었던 문제와 유사한 prefix 문제. 근데 이번엔 Hard 난이도다..
1. Python
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
ans = []
s = set()
cnt = 0
string = ""
for word in words :
# Save all prefix of words[i]
for i in range(len(word)):
string += word[i]
s.add(string)
# Calculate cnt
for word2 in words :
temp = word2
while temp:
if temp in s :
cnt += 1
temp = temp[:-1]
# update ans list
ans.append(cnt)
cnt = 0
string = ""
s.clear()
return ans간단한 예제는 통과가 되는데, 또 무지막지하게 긴 string들이 있는 test case에선 time limit이 걸린다.
아오 진짜...
답지를 보니까 Trie Node를 쓰라고 한다. 그래야 시간이 빨라진다고...
멀고도 험한 Data Structure의 세계이다.
class TrieNode:
def __init__(self):
self.children = {}
self.score = 0
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
root = TrieNode()
# Build Trie with all words
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.score += 1
# Calculate prefix scores for each word
result = []
for word in words:
node = root
total_score = 0
for char in word:
node = node.children[char]
total_score += node.score
result.append(total_score)
return result
이해하고 나니까 뭔가 깰꼼했던 Data 구조이다.
이걸 이제 혼자 힘으로 C++로 옮겨보자.
C로 옮기는 건 언감생심!
혼자 힘 X, GPT Support 조금 받긴 했음.
2. C++
class Tree{
public:
map<char,Tree*> m;
int score;
Tree():score(0){}
~Tree(){
for(auto& pair : m){
delete pair.second;
}
}
};
class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
Tree* root = new Tree();
for(string word : words){
Tree* node = root;
for(char ch : word){
if(node->m.find(ch)==node->m.end()){
node->m[ch] = new Tree();
}
node = node->m[ch];
node->score += 1 ;
}
}
vector<int> ans;
for (string word : words) {
Tree* node = root;
int prefixScore = 0;
for (char ch : word) {
node = node->m[ch];
prefixScore += node->score;
}
ans.push_back(prefixScore);
}
delete root;
return ans;
}
};