Replace Words

class Solution {
    struct Node {
        Node* child[26]{};
        bool isEnd = false;
    };
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Node* root = new Node();
        for (auto& w : dictionary) {
            Node* cur = root;
            for (char c : w) {
                int i = c - 'a';
                if (!cur->child[i]) cur->child[i] = new Node();
                cur = cur->child[i];
            }
            cur->isEnd = true;
        }
        string ans, word;
        sentence.push_back(' ');
        for (char c : sentence) {
            if (c == ' ') {
                Node* cur = root;
                int matched = 0;
                for (int i = 0; i < (int)word.size(); ++i) {
                    int idx = word[i] - 'a';
                    if (!cur->child[idx]) break;
                    cur = cur->child[idx];
                    ++matched;
                    if (cur->isEnd) break;
                }
                if (cur && cur->isEnd) ans.append(word, 0, matched);
                else ans.append(word);
                ans.push_back(' ');
                word.clear();
            } else {
                word.push_back(c);
            }
        }
        if (!ans.empty()) ans.pop_back();      // trim trailing space
        return ans;
    }
};

import "strings"

type rwNode struct {
    child [26]*rwNode
    isEnd bool
}

func replaceWords(dictionary []string, sentence string) string {
    root := &rwNode{}
    for _, w := range dictionary {
        cur := root
        for i := 0; i < len(w); i++ {
            idx := w[i] - 'a'
            if cur.child[idx] == nil {
                cur.child[idx] = &rwNode{}
            }
            cur = cur.child[idx]
        }
        cur.isEnd = true
    }
    words := strings.Split(sentence, " ")
    for i, w := range words {
        cur := root
        matched := 0
        found := false
        for j := 0; j < len(w); j++ {
            idx := w[j] - 'a'
            if cur.child[idx] == nil {
                break
            }
            cur = cur.child[idx]
            matched++
            if cur.isEnd {
                found = true
                break
            }
        }
        if found {
            words[i] = w[:matched]
        }
    }
    return strings.Join(words, " ")
}

from typing import List

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root: dict = {}
        END = '#'
        for w in dictionary:
            cur = root
            for c in w:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
            cur[END] = True

        words = sentence.split(' ')
        for i, w in enumerate(words):
            cur = root
            matched = 0
            found = False
            for c in w:
                if c not in cur:
                    break
                cur = cur[c]
                matched += 1
                if END in cur:
                    found = True
                    break
            if found:
                words[i] = w[:matched]
        return ' '.join(words)

function replaceWords(dictionary, sentence) {
    const root = {};
    const END = '#';
    for (const w of dictionary) {
        let cur = root;
        for (const c of w) {
            if (!(c in cur)) cur[c] = {};
            cur = cur[c];
        }
        cur[END] = true;
    }
    const words = sentence.split(' ');
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        let cur = root;
        let matched = 0;
        let found = false;
        for (const c of w) {
            if (!(c in cur)) break;
            cur = cur[c];
            matched++;
            if (END in cur) {
                found = true;
                break;
            }
        }
        if (found) words[i] = w.substring(0, matched);
    }
    return words.join(' ');
}

class TrieNode {
    TrieNode[] child = new TrieNode[26];
    boolean isEnd = false;
}

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String w : dictionary) {
            TrieNode cur = root;
            for (int i = 0; i < w.length(); i++) {
                int idx = w.charAt(i) - 'a';
                if (cur.child[idx] == null) cur.child[idx] = new TrieNode();
                cur = cur.child[idx];
            }
            cur.isEnd = true;
        }
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            TrieNode cur = root;
            int matched = 0;
            boolean found = false;
            for (int j = 0; j < w.length(); j++) {
                int idx = w.charAt(j) - 'a';
                if (cur.child[idx] == null) break;
                cur = cur.child[idx];
                matched++;
                if (cur.isEnd) {
                    found = true;
                    break;
                }
            }
            if (found) words[i] = w.substring(0, matched);
        }
        return String.join(" ", words);
    }
}

type TrieNode = { [key: string]: TrieNode | boolean };

function replaceWords(dictionary: string[], sentence: string): string {
    const root: TrieNode = {};
    const END = '#';
    for (const w of dictionary) {
        let cur: TrieNode = root;
        for (const c of w) {
            if (!(c in cur)) cur[c] = {};
            cur = cur[c] as TrieNode;
        }
        cur[END] = true;
    }
    const words = sentence.split(' ');
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        let cur: TrieNode = root;
        let matched = 0;
        let found = false;
        for (const c of w) {
            if (!(c in cur)) break;
            cur = cur[c] as TrieNode;
            matched++;
            if (END in cur) {
                found = true;
                break;
            }
        }
        if (found) words[i] = w.substring(0, matched);
    }
    return words.join(' ');
}