原文題目

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

題目摘要

1. 題目描述：實作一個Trie資料結構，用於高效儲存和檢索字串。此資料結構需要提供以下功能：
   • Trie()：定義 Trie 物件。
   • void insert(String word)：插入字串 word 到 Trie 中
   • boolean search(String word)：檢查Trie中是否存在字串 word
   • boolean startsWith(String prefix)：檢查Trie中是否存在以 prefix 開頭的字串
2. 輸入：插入的字串 word 、查詢的字串 word 、檢查的字串前綴 prefix
3. 輸出：如果字串存在Trie中，回傳 true，否則回傳 false；且如果有字串以 prefix 開頭，回傳 true，否則回傳 false

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

解題思路

1. 設計 Trie 結構：
   • 每個 Trie 節點使用哈希表來儲存子節點，鍵是字母、值是對應的子節點（Trie）。
   • 每個節點還需要一個boolean值用於標記該節點是否為某個字串的結尾。
2. insert 方法：
   • 從根節點開始，逐字遍歷要插入的字串。
   • 檢查當前字母的節點是否存在於當前節點的子節點中。如果不存在，則創建一個新的節點並將其加入到子節點中。
   • 移動到對應字母的子節點，繼續處理下一個字母。
   • 當整個字串插入完成後，將最後一個節點的 isEndOfWord 設為 true，表示這是一個完整的字串。
3. search 方法：
   • 從根節點開始，一個個遍歷要搜尋的字串。
   • 檢查每個字母的節點是否存在。如果某個字母的節點不存在，回傳 false。
   • 遍歷完成後，檢查最後一個節點的 isEndOfWord 是否為 true，以確定該字串是否存在於 Trie 中。
4. startsWith 方法：
   • 從根節點開始，一個個遍歷要檢查的前綴。
   • 檢查每個字母的節點是否存在。如果某個字母的節點不存在，回傳 false。
   • 如果遍歷完成，則表示 Trie 中存在以該前綴開頭的字串，回傳 true。

程式碼

class Trie {
    Map<Character, Trie> children; //用哈希表儲存子節點（字母）
    boolean isEndOfWord; //標記當前節點是否為某個字串的結尾
    public Trie() {
        children = new HashMap<>(); //定義子節點為空
        isEndOfWord = false; //預設不是結尾
    }
    public void insert(String word) {
        //從Trie的根節點開始追蹤
        Trie node = this;
        for (char ch : word.toCharArray()) {
            //如果當前字母的子節點不存在，則創建一個新節點
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new Trie());
            }
            //移動到該字母對應的子節點，繼續處理下一個字母
            node = node.children.get(ch);
        }
        node.isEndOfWord = true; //標記最後一個節點為字串的結尾
    }
    public boolean search(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            //如果當前字母不存在於當前節點的子節點中，則直接回傳false
            if (!node.children.containsKey(ch)) {
                return false;
            }node = node.children.get(ch);
        }
        return node.isEndOfWord; //檢查最後一個節點是否為字串的結尾
    }
    public boolean startsWith(String prefix) {
        Trie node = this;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }node = node.children.get(ch);
        }
        //如果前綴的所有字母都能成功匹配，回傳true
        return true;
    }
}

結論： Trie字典樹的例子其實很常見，就像是你在手機輸入法中看到的預測字詞、自動補全功能。當你開始輸入一個單字時，Trie 會立即幫你查找已經輸入過的字，並給出建議，讓你更快完成輸入。想像一下，在搜尋引擎中搜尋時，Trie 也能迅速判斷你的關鍵字是否存在，並提供相關的結果。無論是平時聊天打字還是做日常搜尋時，這種設計讓我們在日常生活中享受更流暢的輸入和搜尋體驗，讓每一次的打字變得輕鬆又快速！