Trie

208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

 

 

---

513. Find Bottom Left Tree Value

https://leetcode.com/problems/design-add-and-search-words-data-structure

 

 

 

 

TrieNode, Map으로 해결

class WordDictionary {
    private class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEnd;

        TrieNode() {
            children = new HashMap<>();
            isEnd = false;
        }
    }

    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return searchRecursive(word, 0, root);
    }

    private boolean searchRecursive(String word, int index, TrieNode node) {
        if (node == null) {
            return false;
        }
        if (index == word.length()) {
            return node.isEnd;
        }

        char ch = word.charAt(index);
        if (ch == '.') {
            // '.' 와일드카드는 모든 가능한 문자 탐색
            for (TrieNode child : node.children.values()) {
                if (searchRecursive(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            // 특정 문자 탐색
            return searchRecursive(word, index + 1, node.children.get(ch));
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

 

class Trie:
  def __init__(self):
    self._root = TrieNode()   
    
  def _recurAdd(self,node:TrieNode, word:str) -> None:
    if len(word) == 0:
      node.isEnd = True
      return
    
    ch = word[0]
    next_link = node.links.get(ch)
    if next_link is None:      
      node.links[ch] = TrieNode()
      next_link = node.links[ch]
    self._recurAdd(next_link,word[1:])
    

  def add(self, word: str) -> None:
    if len(word) == 0:
      return
    
    self._recurAdd(self._root,word)
    
    
  def _recurSearch(self, node:TrieNode, word: str) -> bool:    
    if len(word) == 0:
      isEnd = node.isEnd
      return isEnd
    
    ch = word[0]
    if ch == '.':
      letters = node.links.keys()
      for key in letters:
        ret = self._recurSearch(node.links[key],word[1:])
        if ret is True:
          return True
      return False       
      
    else:
      next_link = node.links.get(ch)
      if next_link:
        return self._recurSearch(next_link,word[1:])
      return False


  def search(self, word: str) -> bool:
    if len(word) == 0:
      return True
    
    return self._recurSearch(self._root,word)

 

 

 

root의 자료구조는 Array를 써도되고, HashMap을 써도 된다.

array를 사용하는 경우

• root -> 24자리의 배열
• 두번째 노드에도->  24자리의 배열
• 세번째 노드에도->  24자리의 배열

 

isEnd를 사용해서 단어의 마지막인지 체크하면 된다.

 

 

HashMap의 경우

 

1) iterative

2) reculsive -> 함수 호출 스택