Leet Code Daily 2024-06-07 - Replace Words

constexpr int kMaxChars = 26;

typedef struct trie trie;

struct trie {
    bool isRoot;
    trie* children[kMaxChars];
};

trie* trieNew() {
    trie* ret = new trie();
    ret->isRoot = false;
    for (int c = 0; c < kMaxChars; c++) {
        ret->children[c] = nullptr;
    }
    return ret;
}

trie* trieSeek(trie* current, char c) {
    int key = c - 'a';
    if (current->children[key] == nullptr) {
        current->children[key] = trieNew();
    }
    return current->children[key];
}

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        trie* root = trieNew();
        for (const auto& word : dictionary) {
            trie* current = root;
            for (const auto& c : word) {
                current = trieSeek(current, c);
            }
            current->isRoot = true;
        }

        string ret;
        trie* current = root;
        for (const auto& c : sentence) {
            if (c == ' ') {
                current = root;
                ret += c;
            } else if (!current->isRoot) {
                current = trieSeek(current, c);
                ret += c;
            }
        }
        return ret;
    }
};