[LeetCode] 648. Replace Words

https://leetcode.com/problems/replace-words/description/

leetcode - Replace Words

문제 유형 :  문자열 처리, 트라이(Trie)

문제 난이도 : Medium

 

문제

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

 

dictionary 문자열 배열과 문자열 sentence가 주어진다.

sentence들의 각 단어의 전위부가  dictionary로 되어있다면 대체할 수 있습니다.

문자열을 최대한 줄여서 반환하시오.

 

풀이

Trie를 이용하여 전위부 처리를 효율적으로 해낼 수 있다.

Trie는 부모가 전위부가 되는 트리이다.

dictionary의 단어들로 Trie를 구성해주고, 단어를 넣어 Trie에 검색하면, 전위부를 얻어 대체할 수 있다.

없으면 그대로 문자열에 넣는다.

빨간점은 루트부터 그 지점까지 읽었을 때, dictionary에 있음을 의미하여 찍었다.

 

코드

C++

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

class TrieNode {
public:
    bool isEnd;
    TrieNode* children[26];
    
    TrieNode() : isEnd(false) {
        fill(begin(children), end(children), nullptr);
    }
};

class Trie {
public:
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }
    
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) {
                node->children[c - 'a'] = new TrieNode();
            }
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }
    
    string getPrefix(const string& word) {
        TrieNode* node = root;
        string prefix = "";
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) {
                break;
            }
            node = node->children[c - 'a'];
            prefix += c;
            if (node->isEnd) {
                return prefix;
            }
        }
        return word;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie trie;
        for (const string& word : dictionary) {
            trie.insert(word);
        }
        
        stringstream ss(sentence);
        string word;
        string ans = "";
        
        while (ss >> word) {
            if (!ans.empty()) {
                ans += " ";
            }
            ans += trie.getPrefix(word);
        }
        
        return ans;
    }
};