#208 Implement Trie (Prefix Tree)

전우재·2023년 9월 11일

leetcode

목록 보기

19/21

문제링크 - https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

문제 조건

1 <= word.length, prefix.length <= 2000
word prefix는 영문 소문자로만 구성된다.
insert, search, startsWith의 최대 호출 횟수는 3*10^4.
접두사 트리를 구현하는 것이 목표이다. 해당 트리는 문자열 검색 시 자동완성이나 맞춤법검사 기능 구현시 유용하다.

문제 해결

문제 해결 로직

트리를 사용하여 단어를 저장한다.
- 노드는 하나의 character를 가지도록 한다.
- 단어를 저장할 때 끝지점을 알 수 있도록 표시할 변수를 사용한다.
문자열을 찾기 위해 다음과 같은 조건을 만족해야 찾은 것으로 간주한다.
- 글자 위치와 노드 깊이에 같은 글자가 있는지
- 글자 크기만큼 돌았을 때 남은 노드가 없는지
startWith은 검색 조건 중 남은 노드가 있어도 되도록 한다.

데이터 입력

트리의 노드를 나타낼 클래스가 필요하다.

Node
- 각 노드는 자식 노드children을 가지고 있다.
- booleanisEndOfWord를 가지고 있어 해당 문자가 끝나는 지점인지 알 수 있다.
root Trie는 생성 시 root Node를 가지고 있다.
Node 구현 코드

public class Node{
      public Map<Character, Node> children;
      public boolean isEndOfWord;

      public Node() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
      }
}

데이터 insert

데이터 저장 함수 insert는 다음과 같은 작업들이 필요하다.
- 노드 생성하여 character 넣기
- 현재 위치가 단어 끝부분인지 표시하기
1. 기존에는 String word만 인수로 받지만 재귀 함수로 나타내기 위해 Node도 받는 함수가 되도록 한다.
1. 재귀 사용 시 종료 조건을 정하도록 한다.
- 현재는 입력받은 단어를 앞에서 부터 하나씩 노드로 만들어 진행하려 한다.
- 따라서 종료하기 위한 조건은 입력받은 단어가 없을 때, 해당 위치의 노드가 문자열의 끝임을 확인할 수 있는 변수를 변경한다.
1. character 찾기
- 입력받은 string에서 chatAt을 통해 글자를 떼어내고, 현재 깊이 노드에서 해당 key로 찾는다.
- 만약 해당 key가 없다면 생성한다.
- 만약 이미 key가 있다면 해당 노드로 깊이를 이동하여 남은 글자의 저장 작업을 진행한다.

    public void insert(String word) {
      insert(this.root, word);
    }

    private void insert(Node node, String word) {
      if (word.length() == 0) {
          node.isEndOfWord = true;
          return;
      }

      char c = word.charAt(0);
      Node child = node.children.get(c);

      if (child == null) {
          child = new Node(); // 자식 노드가 없으면 생성
          node.children.put(c, child);
      }

      insert(child, word.substring(1));
    }

데이터 search

데이터 저장 함수 search와 startsWith은 비슷한 로직으로 해결할 수 있다.
- search는 받은 단어의 모든 character가 깊이에 맞춰 모두 있어야 한다.(모두 일치)
- startsWiths는 받은 단어만큼만 순서대로 트리에 있으면 된다.(일부 일치)
이번에는 재귀가 아닌 반복문으로 간단하게 풀어보도록 하였다.

root 위치를 잠시 받을 변수를 선언한다.
입력받은 글자 수 만큼 글자를 쪼개어 탐색한다.
글자 하나씩 탐색하며 트리에 있는지 확인한다.
3-1. 만약 트리에 해당 값을 가진 노드가 없다면 false를 반환한다.
3-2. 해당 값을 가진 노드가 있다면 현재 위치를 해당 노드 위치로 이동한다.
노드 끝까지 반복하였다면 현재 node의 값을 반환한다.(word의 끝부분 까지 찾음 && 노드 끝부분 까지 찾음)

startsWith은 기존 search 로직에서 마지막 확인 부분인 노드 끝부분 까지 찾았다는 것을 확인하지 않도록 하면 된다.

    public boolean search(String word) {
        Node child = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!child.children.containsKey(c)) {
                return false;
            }
            child = child.children.get(c);
        }
        return child.isEndOfWord;
    }

코드 작성

class Trie {
    public class Node{
      public Map<Character, Node> children;
      public boolean isEndOfWord;

      public Node() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
      }
    }

    private Node root;

    public Trie() {
      this.root = new Node();
    }
    
    public void insert(String word) {
      insert(this.root, word);
    }

    private void insert(Node node, String word) {
      if (word.length() == 0) {
          node.isEndOfWord = true;
          return;
      }

      char c = word.charAt(0);
      Node child = node.children.get(c);

      if (child == null) {
          child = new Node(); // 자식 노드가 없으면 생성
          node.children.put(c, child);
      }

      insert(child, word.substring(1));
    }

    
    public boolean search(String word) {
        Node child = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!child.children.containsKey(c)) {
                return false;
            }
            child = child.children.get(c);
        }
        return child.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        Node child = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (!child.children.containsKey(c)) {
                return false;
            }
            child = child.children.get(c);
        }
        return true;
    }
}