[ Top Interview 150 ] 208. Implement Trie (Prefix Tree)

문제

208. Implement Trie (Prefix Tree)

 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.

Tries

• 트리의 일종으로 ”문자열의 키”를 효율적으로 저장하고 검색하기 위한 자료구조
• 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다
• 한 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다

문제 해결 전략

• void insert(String word)

  • 맨 앞글자를 key, 나머지 글자를 통해 만든 Trie를 value로 하는 Map을 이용
  • key에 해당하는 value가 있다면, 재귀적으로 insert(substring)을 하고, 없다면 새로 만들어서 넣은 후에 재귀적으로 insert(substring)을 요청한다.
    • substring : word에서 맨 앞글자를 제거한 string

• boolean search(String word)

  • Map에 word의 맨 앞글자를 key로 하는 값을 요청한다.
    • 해당 값이 없다면, false를 반환
  • 재귀적으로 search(String substring)를 요청하도록 함
  • substring의 길이가 0인 경우, 해당 문자로 끝나는지 확인함 (isEnd)

• boolean startsWith(String prefix)

  • Map에 word의 맨 앞글자를 key로 하는 값을 요청한다.
    • 해당 값이 없다면, false를 반환
  • 재귀적으로 startsWith(String substring)를 요청하도록 함
  • substring의 길이가 0인 경우, true를 반환

1차 답안 & 중복 제거

• 1차 답안 (최대한 통과시키는 것에 집중함)

  class Trie {
  
      private final Map<Character, Trie> children;
      private boolean isEnd;
  
      public Trie() {
          children = new HashMap<>();
          isEnd = false;
      }
  
      public void insert(String word) {
          if (word.length() == 0) {
              isEnd = true;
              return;
          }
  
          Character key = word.charAt(0);
          Trie child = children.get(key);
          if (child == null) {
              child = new Trie();
              children.put(key, child);
          }
  
          child.insert(word.substring(1));
      }
  
      public boolean search(String word) {
          if (word.length() == 0) {
              return isEnd;
          }
  
          Character key = word.charAt(0);
          Trie child = children.get(key);
          if (child == null) {
              return false;
          }
          return child.search(word.substring(1));
      }
  
      public boolean startsWith(String prefix) {
          if (prefix.length() == 0) {
              return true;
          }
  
          Character key = prefix.charAt(0);
          Trie child = children.get(key);
          if (child == null) {
              return false;
          }
          return child.startsWith(prefix.substring(1));
      }
  }

• 리팩토링 제거

  • 중복된 코드를 메서드로 묶어내는 것에 집중함

  class Trie {
  
      private final Map<Character, Trie> children;
      private boolean isEnd;
  
      public Trie() {
          children = new HashMap<>();
          isEnd = false;
      }
  
      public void insert(String word) {
          if (word.length() == 0) {
              isEnd = true;
              return;
          }
  
          Trie child = getChild(word);
          if (child == null) {
              child = putNewChild(word);
          }
          child.insert(word.substring(1));
      }
  
      public boolean search(String word) {
          if (word.length() == 0) {
              return isEnd;
          }
  
          Trie child = getChild(word);
          return child != null && child.search(word.substring(1));
      }
  
      public boolean startsWith(String prefix) {
          if (prefix.length() == 0) {
              return true;
          }
  
          Trie child = getChild(prefix);
          return child != null && child.startsWith(prefix.substring(1));
      }
  
      private Trie getChild(String word) {
          Character key = word.charAt(0);
          return children.get(key);
      }
  
      private Trie putNewChild(String word) {
          Character key = word.charAt(0);
          Trie child = new Trie();
          children.put(key, child);
          return child;
      }
  }

  

  2차 답안

  • Map으로 구현한 것을 배열로 바꿈
    • a는 0번째 ~ z는 25번째의 형식으로 구현
    • getChild, putNewChild를 분리해 놓아 자료구조를 바꾸기 용이했다.
    • Map 대신 배열을 사용해서 성능을 높일 수 있었다.

  class Trie {
  
      private static final int COUNT_OF_LETTERS = 26;
      private static final char START_LETTER = 'a';
  
      private final Trie[] children;
      private boolean isEnd;
  
      public Trie() {
          children = new Trie[COUNT_OF_LETTERS];
          isEnd = false;
      }
  
      public void insert(String word) {
          if (word.length() == 0) {
              isEnd = true;
              return;
          }
  
          Trie child = getChild(word);
          if (child == null) {
              child = putNewChild(word);
          }
          child.insert(word.substring(1));
      }
  
      public boolean search(String word) {
          if (word.length() == 0) {
              return isEnd;
          }
  
          Trie child = getChild(word);
          return child != null && child.search(word.substring(1));
      }
  
      public boolean startsWith(String prefix) {
          if (prefix.length() == 0) {
              return true;
          }
  
          Trie child = getChild(prefix);
          return child != null && child.startsWith(prefix.substring(1));
      }
  
      private Trie getChild(String word) {
          char key = word.charAt(0);
          return children[key - START_LETTER];
      }
  
      private Trie putNewChild(String word) {
          char key = word.charAt(0);
          Trie child = new Trie();
          children[key - START_LETTER] = child;
          return child;
      }
  }