[LeetCode/JAVA] 208. Implement Trie (Prefix Tree)

문제

trie라는 트리 데이터 구조를 구현하는 문제이다.

Trie() 는 trie 객체의 시작을 구현해야하고, insert()는 word라는 문자열을 trie 트리에 입력을 구현, search()는 문자열 word가 trie에 존재하는지를 구현하고, startsWith()는 접두사 문자열 prefix가 주어질 때 접두사가 일치하는 단어가 존재하는지를 구현해야한다.

풀이

일단 해당 문제는 소문자로만 이루어진 문자열을 활용해서 String을 char로 변환해서 트리 노드에 하나씩 저장하는 방식을 먼저 구현해야했다. 그리고 노드를 타고 하위 노드로 내려갔을 때, 해당하는 단어가 단순한 문자열의 나열인지 실제 단어인지를 판단 할 수 있어야 했다.

왜냐하면 예시를 보면

apple이라는 단어가 insert 되어있고 apple이라는 단어를 search하면 True를 반환한다. 하지만 app이라는 단어를 search하면 False를 반환하는 것을 볼 수 있다. 단순히 노드의 순서가 a -> p -> p -> l -> e 순으로 조회될텐데, 이미 app이라는 문자열은 존재한다. 하지만 이를 구분하기 위해 노드의 상태를 판단할 수 있도록 변수를 설정해줘야한다.

다음으로 소문자로만 이루어진 문자열만 주어진다는 점이다. 소문자로 이루어진 영어 문자열만 주어지면 하나의 노드는 자식 노드를 a ~ z 까지 최대 26개의 하위 노드를 가질 수 있다. 이 점을 고려해서 노드 객체를 생성해야 한다.

(1) - 문제의 시작은 Trie()라는 트리를 생성하는 메소드를 먼저 실행한다. root라는 변수를 가진 노드를 가장 먼저 생성해준다. 그리고 해당 변수는 모든 메소드에서 공통적으로 사용되는 시작 노드이므로 멤버 변수로 선언시켜 둔다.

(2) - 가장 먼저 insert() 메소드를 구현하기 위해 root 부터 시작하고, 주어진 word라는 문자열을 하나씩 체크한다. 여기서 자식 노드에 해당하는 문자가 존재한다면 해당 노드로 이동, 아니라면 새로운 자식 노드를 생성해준다. 그리고 모든 문자열을 반복하여 트리에 저장했다면, 해당 노드까지 오게 된다면 이는 문자라는 상태를 표현하기 위해 isWord를 True로 설정해준다.

(3) - search() 메소드는 주어진 word 문자열을 문자 단위로 하나씩 체크해서 트리에 모든 문자열이 순서대로 노드에 저장되어 있는지 체크를 해야한다. 만약 해당하는 문자의 자식노드가 존재하지 않는다면 false를 반환해서 search 메소드를 종료하고, 아니라면 계속해서 반복한다. 마지막 문자 까지 성공적으로 도달한다면, isWord라는 값을 반환한다. 이는 앞서 설명했듯이 apple과 app의 예시처럼 예외가 발생할 수 있기 때문이다.

(4) - startsWith() 메소드는 search() 메소드와 비슷한 원리이다. 마지막에 apple과 app의 예시의 예외를 생각하지 않고 성공적으로 prefix라는 문자열을 찾을 수 있다면, 무조건 true를 반환하면 된다.

코드

class TrieNode {
    public boolean isWord;
    public TrieNode[] children = new TrieNode[26];
}

public class Trie {
// (1)
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
// (2)
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }
// (3)
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return node.isWord;
     }
// (4)
     public boolean startsWith(String prefix) { 
        	TrieNode node = root; 
        	for (char c : prefix.toCharArray()) { 
        		if(node.children[c-'a']==null) return false; 
        		node=node.children[c-'a']; 
        	} 

        	return true;  
      }  
}