[leetcode 208번] Implement Trie (Prefix Tree) (JAVA)

1.문제

Implement Trie (Prefix Tree) - LeetCode

Implement Trie (Prefix Tree) - LeetCode

---

2.문제설명

 

• 이 문제는 Trie 를 구현 하라는 트리 자료구조 문제이다.
• Trie 의 경우 문자열을 검색하는 알고리즘에 주로 사용된다.
• 구현 해야할 것은 Tree 생성자와 Insert , search , StartsWith 메서드를 구현해야한다.
• Insert 는 단어를 트리에 저장해야한다.
• Search 는 찾으려는 단어가 Tree 에 저장되어있는지 여부를 체크
• StartsWith 는 찾으련느 단어가 시작되는 단어가 있는지 여부를 체크

---

3.소스코드

class Trie {
     private Node root;

   public Trie(){
        this.root = new Node();
    }
    private static class Node {
        Node[] children;
        boolean isWord;

        public Node() {
            children = new Node[26];
            isWord = false;
        }
    }
    
   public void insert(String word) {
        Node tmp = root;
        for(int i =0; i<word.length(); i++){
            int idx = word.charAt(i) - 'a';

            if(tmp.children[idx] == null){
                tmp.children[idx] = new Node();
            }
            tmp = tmp.children[idx];
        }
        tmp.isWord =true;
    }

    public boolean search(String word) {
        Node tmp = root;

        for(int i=0; i<word.length(); i++){
            int idx = word.charAt(i) - 'a';

            if(tmp.children[idx] == null){
                return false;
            }else{
                tmp = tmp.children[idx];
            }
        }
        return !tmp.isWord ? false : true;
    }

    public boolean startsWith(String prefix) {
        Node tmp = root;

        for(int i=0; i<prefix.length(); i++){
            int idx = prefix.charAt(i) - 'a';

            if(tmp.children[idx] == null){
                return false;
            }else {
                tmp = tmp.children[idx];
            }
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

---

4.소스코드 해설

Tree 자료구조를 활용하여 Trie 검색 알고리즘을 구현하기 위해서는 우선 입력 받은 문자열을 트리에 하나씩 저장해야한다. 이때 "apple" 이라고 하면 'a' 를 정수로 변환하여 각 노드의 자식 노드에 추가 시키는 것이다.

 

위에 있는 Node 를 구현 하기 위해서는 하위노드를 가지고 있는 Node와 찾으려고하는 문자열인지 판단하는 boolean 값 을 가지고 있는 class Node 가 필요하다.

 

Insert() 메서드를 구현 하기 위해서는 Node 의 root 를 시작으로 전달 받은 문자열의 길이 만큼 순회하면서 정수로 변환된 문자를 하나씩 집어 넣어 주는 코드가 필요하다 그 이후 이 노드가 문자열에 입력된것을 판단하기 위한 Boolean  값을 변환하여 insert 한다.

 

Search() 메서드는 insert와 비슷 하지만 만약 순회하는 도중 insert 된 Node 에 null 로 비어 있으면 false 로 반환하고 모두 순회를 정상적으로 돌아간다면 그 입력받은 문자열은 존재하므로 true 를 반환하게 한다.

 

StartsWith () 메서드는  Search 와 같은 방법으로 Node 를 순회한다. 모두 순회시 True 중간에 null 을만나면 False 이다.

---

5. 회고

문제 파악에서 알파벳을 조건으로 찾기 때문에 [26] 이라는 공간을 잡아 준 것과 StartsWith 와 Search 를 같은 느낌이지만 정확히 다른 메서드라는 것을 인식하면서 코딩 하게 되었다.  word 를 검색하는것과 prefix  앞에있는 단어를 검색하는 것은 전혀 다른개념으로 처음 Search를 그냥 호출 해서 사용하면 되지않을까? 라는 생각으로 호출 했지만 결과는 역시 틀렸다 단순히 검색한다는 개념에서 부분검색을 하는 것을 생각하여 한번더 생각 하게 되는 문제였다.

 

이 문제를 풀때는 트라이 알고리즘을 쓴다 생각하여  시간 복잡도는 O(N) 이고

공간 복잡도는 O(알파벳^N) 이 될것이다. 

최악의 경우 엄청 긴 길이를 가진 트리의 depth 만큼 길어지기 때문에 알파벳 26 의 제곱을 가지게 될것이다.