211. Design Add and Search Words Data Structure - Medium

前往題目

想法

• 可搜尋字詞功能我第一個想法是建構一顆樹(Trie)，字母連著字母
• 這題是資料結構，比較好玩一點😆

思路

1. Trie的資料結構，用array儲存字母，因為固定最多26個
2. 加入就直接判斷有沒有該字母，沒有的話init.有的話直接略過，看下一個
3. Search用Backtracking的方式加入帶有.的詞

比較妙的是backtracking的部分，參照以下的code可以看到，遇到.的時候就會疊代當前trie node的每一個child，在每個child裡都再call一次searchHelper以檢查接下來的字母，這裡蠻tricky的，比較難想出來

Code

search的部分沒有想出來，參考了Neetcode大大的影片

class WordDictionary {
    private class Trie {
        char c;
        Trie[] children;
        boolean isWord;

        public Trie(char c) {
            children = new Trie[26];
            isWord = false;
            this.c = c;
        }
    }

    Trie root;

    public WordDictionary() {
        root = new Trie('\0'); // Init.
    }
    
    public void addWord(String word) {
        // Maintain root
        Trie curr = root;

        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);

            // Check if already init.
            if (curr.children[c - 'a'] == null) {
                // Init. and add
                curr.children[c - 'a'] = new Trie(c);
            }
            // switch the current trie
            curr = curr.children[c - 'a'];
        }
        // Mark the end of the word
        curr.isWord = true;
    }
    
    public boolean search(String word) {
        return searchHelper(word, root, 0);
    }

    private boolean searchHelper(String word, Trie curr, int index) {
        for (int i = index; i < word.length(); ++i) {
            char c = word.charAt(i);

            if (c == '.') {
                for (Trie t : curr.children) {
                    // Search the next char
                    if (t != null && searchHelper(word, t, i + 1)) {
                        return true;
                    }
                }
                return false;
            }

            // Word does not exist
            if (curr.children[c - 'a'] == null) {
                return false;
            }
            
            // Next char
            curr = curr.children[c - 'a'];
        }
        return curr.isWord;
    }


}

2024/04/22

• search的時候有點掙扎，複習了才寫出來