[LeetCode] 2416. Sum of Prefix Scores of Strings

https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/?envType=daily-question&envId=2024-09-25

leetcode - Sum of Prefix Scores of Strings

문제 유형 : 트라이(Trie), 구현

문제 난이도 : Hard

 

문제

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.

 

길이가 1 이상이 단어를 N개 가진 words배열이 주어진다.

우리는 words[i]에 있는 각 단어의 각 접두사가 배열에서 얼마나 나오는지에 따라 점수를 매길 것이다.

 

예를 들어, ["a", "ab", "abc", "cab"]에서, "ab"의 점수는 2이다. "ab"는 "ab"와 "abc"의 접수다가 될 수 있기 때문이다.

words[1]의 점수는 5이다. "a"로 3점, "ab"로 2점으로, 3+2 = 5점이다.

words[i]의 점수를 각각 answer[i]에 담아 반환하시오.

문자열 자체는 스스로의 접두사가 될 수 있습니다.

 

풀이

Trie를 만들어서 해결할 수 있다.

Trie의 각 노드에 카운트를 저장하여 빈도를 누적시키도록 한다.

words의 모든 단어를 하나씩 Trie에 추가한다.

추가하면서, 방문하는 노드들에 대해 카운트를 1씩 늘린다.

그리고, 모든 단어들을 한 번씩 다시 넣어서 순회시키면서, 카운트를 누적시킨 값을 반환받는다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class TrieNode {
public:
    char val;
    int cnt;
    TrieNode* children[26];

    TrieNode(char val) {
        this -> val = val;
        cnt = 0;
        for(int i = 0; i < 26; ++i) {
            children[i] = NULL;
        }
    }
};

class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode('-');
    }

    void addWord(string word) {
        auto curr = root;

        for(char prefix : word) {
            if (curr -> children[prefix - 'a'] == NULL) curr -> children[prefix - 'a'] = new TrieNode(prefix);
            curr = curr -> children[prefix - 'a'];
            curr -> cnt++;
        }
    }

    int getScore(string word) {
        auto curr = root;
        int res = 0;
        for(char prefix : word) {
            curr = curr -> children[prefix - 'a'];
            res += curr -> cnt;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        Trie* t = new Trie();
        for(const auto &word : words) {
            t -> addWord(word);
        }

        vector<int> ans;
        for(const auto &word : words) {
            ans.push_back(t -> getScore(word));
        }

        return ans;
    }
};