Trie Class 구현 시 주의해야 할 부분

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

Implement Trie (Prefix Tree) - LeetCode

Trie 의 insert 함수를 구현 할 때 주의사항이 있음

아래 insert1 과 insert2 함수 중에 어떤 코드가 제대로 동작할까? 답은 insert2 만 제대로 insert 되고, insert1 은 insert가 제대로 되지 않는다. curr.children[c-'a'] 로 다음 자식 노드를 가리키게 되는데, 이 때 새 Node node 에 curr.children[c-'a'] 값을 할당하면 curr 가 해당 curr.children[c-'a']에 있는 node로 연결이 되지 않는다. 왜냐?? 최초로 trie의 배열에 담길 자식 노드인 curr.children[c-'a'] 는 null 로 선언되기 때문에, curr 와의 관계가 끊어진 것이다. 

 

그림으로 보자.

 

public class Trie {
  
  private Node root;

  public Trie() {
    root = new Node();
  }

  public void insert1(String word){
    if(word.isEmpty() || word.equals("")) return;
    char[] charArr = word.toCharArray();
    Node curr = this.root;
    for(char c : charArr) {
      Node node = curr.children[c-'a'];
      if(node == null) node = new Node();
      curr = node;
    }
    curr.isWord =true;
  }

  public void insert2(String word){
    if(word.isEmpty() || word.equals("")) return;
    char[] charArr = word.toCharArray();
    Node curr = this.root;
    for(char c : charArr) {
      if(curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
      curr = curr.children[c-'a'];
    }
    curr.isWord =true;
  }
  
  public boolean search(String word) {
    char[] charArr = word.toCharArray();
    Node curr = root;
    for(char c : charArr) {
      Node node = curr.children[c-'a'];
      if(node == null) return false;
      curr = node;
    }
    return curr.isWord;
  }
}

class Node{
  Node[] children;
  boolean isWord;
  public Node(){
    children = new Node[26];
    isWord = false;
  }
}