[LeetCode] 648. Replace Words, Medium

1. 문제

• 어간으로 구성된 dictionary와 파생어로 구성된 sentence 문자열이 주어질 때, 파생어 요소 중 어간이 있는 요소는 어간으로 교체하여 반환하라.

2. 해결

class TrieNode {
    children:Map<string, TrieNode>;
    root:string;
    constructor() {
        this.children = new Map();
        this.root = '';
    }
}

class Trie{
    root:TrieNode;
    constructor() {
        this.root = new TrieNode();
    }

    insert(word:string) {
        let node = this.root;

        let root = '';
        for(const char of word) {
            if(!node.children.has(char)){
                node.children.set(char, new TrieNode());
            }

            node = node.children.get(char);
            root += char;
        }

        node.root = root;
    }

    findRoot(word: string): string {
        let node = this.root;

        for (const char of word) {
            if (!node.children.has(char)) {
                return ''; 
            }

            node = node.children.get(char)!;

            if (node.root) {
                return node.root; 
            }
        }

        return ''; 
    }

}

function replaceWords(dictionary: string[], sentence: string): string {
    const trie = new Trie();
    for(const word of dictionary) {
        trie.insert(word);
    }

    const sentenceArr = sentence.split(' ');

    for(let i = 0; i<sentenceArr.length; i++) {
        const root = trie.findRoot(sentenceArr[i]);
        if(root) {
            sentenceArr[i] = root;
        }
    }

    return sentenceArr.join(' ')
};

• 어간으로 구성된 트라이를 만들고, 해당 트라이에서 어간을 발견하면 바로 리턴하여 해당 값으로 교체해준다.