208. Implement Trie (Prefix Tree) - Medium

前往題目

之前寫過，搬運一下

想法

• 大概念是看影片才得來
• 一半是自己照著概念寫出來的
• 但class之間attribute的操作不熟練
• 而且原來inner class的private，包含他的class是可以存取的
• 本來想說要寫get set，但根本不用

思路

1. 新建TrieNode class，用以表示Trie的節點
2. 每個node都有自己的children
3. Trie物件裡新增instance variable作為root
4. 每個function都從root開始一個一個char看
5. 對有或沒有該char做處理

Code

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode('\0'); // Insert dummy node as root
    }
    
    public void insert(String word) {
        TrieNode currNode = root;
        
        // Iterate each character of the words
        for (char c : word.toCharArray()) {
            // Check if not exist
            if (currNode.children[c - 'a'] == null) {
                // Insert if the char is not present
                currNode.children[c - 'a'] = new TrieNode(c);
            }
            // When exist switch to it and go on
            currNode = currNode.children[c - 'a'];
        }
        // Mark the last as the end of the word
        currNode.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode currNode = root;

        for (char c : word.toCharArray()) {
            // Check if not exist
            if (currNode.children[c - 'a'] == null) {
                return false;
            }
            // Switch to the character and keep searching the next
            currNode = currNode.children[c - 'a'];
        }

        // Check the last character is the end of the word
        return currNode.isWord == true;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode currNode = root;

        for (char c : prefix.toCharArray()) {
            // Check if not exist
            if (currNode.children[c - 'a'] == null) {
                return false;
            }
            // Switch to the character and keep searching the next
            currNode = currNode.children[c - 'a'];
        }
        return true;
    }

    class TrieNode {
        private char value;
        private boolean isWord;
        private TrieNode[] children;

        public TrieNode(char val) {
            this.value = val;
            this.isWord = false;
            this.children = new TrieNode[26];
        }
    }
}

2024/01/20

• 大致上自己寫出來了，還是參考了一點之前寫的
• 決定用哪種資料結構的時候還是有些掙扎