[LeetCode] 208. Implement Trie (Prefix Tree)

😎풀이

1. TrieNode 클래스를 선언한다.
   1-1. 해당 클래스는 자식 노드를 저장하며 재귀적인 구조로 검색 가능한지 확인할 수 있다.
   1-2. 문자의 마지막은 isEnd 속성을 통해 확인이 가능하며 이는 search 명령에 활용한다.
2. 생성자의 호출 시에는 TrieNode를 root로 갖는 작업을 진행한다.
3. insert 호출 시 단어의 각 자리는 재귀적인 TrieNode에 입력되며 단어의 마지막엔 isEnd 속성을 true로 설정한다.
4. search 호출 시 재귀적으로 root를 탐색하여 문자를 검색하며 각 자리가 동일한지 확인한 후 최종적으로 isEnd가 단어가 종료될 시점에 true라면 true를 반환하며 이 외에 경우는 false를 반환한다.
5. startsWith 호출 시 재귀적으로 root를 탐색하여 문자를 검색하며 각 자리가 동일한지 확인한 후 문자가 모두 동일할 경우 true를 반환한다.

// Trie의 각 노드를 표현하는 클래스
class TrieNode {
  // 자식 노드를 저장하는 객체 (문자 -> TrieNode)
  children: { [key: string]: TrieNode };
  // 현재 노드가 단어의 끝을 나타내는지 여부
  isEnd: boolean;

  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

// Trie 클래스 정의
class Trie {
  private root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  insert(word: string): void {
    let node = this.root;
    // 단어의 각 문자에 대해
    for (const char of word) {
      // 현재 노드의 자식 중 해당 문자가 없다면 새 TrieNode 생성
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      // 해당 문자에 해당하는 자식 노드로 이동
      node = node.children[char];
    }
    // 단어의 마지막 문자 노드에서 단어의 끝임을 표시
    node.isEnd = true;
  }

  search(word: string): boolean {
    let node = this.root;
    // 단어의 각 문자에 대해
    for (const char of word) {
      // 현재 노드에 해당 문자가 없다면 단어가 존재하지 않음
      if (!node.children[char]) {
        return false;
      }
      // 해당 문자에 해당하는 자식 노드로 이동
      node = node.children[char];
    }
    // 마지막 노드가 단어의 끝을 표시하는 경우에만 단어가 완성된 것으로 간주
    return node.isEnd;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    // 접두사의 각 문자에 대해
    for (const char of prefix) {
      // 현재 노드에 해당 문자가 없다면 접두사를 가진 단어가 없음
      if (!node.children[char]) {
        return false;
      }
      // 해당 문자에 해당하는 자식 노드로 이동
      node = node.children[char];
    }
    return true;
  }
}