[알고리즘] LeetCode - Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) - LeetCode

문제 설명

• 트라이 클래스를 구현해야 한다.
• 작성해야할 클래스 구현체는 아래와 같다.
  • Trie() : 트라이 개체를 초기화 한다.
  • void insert(String word) : 문자열을 word 트라이에 삽입한다.
  • boolean search(String word) : 문자열이 word 트라이에 있으면 true 없으면 false를 반환한다.
  • boolean startsWith(String prefix) : 접두사가 있는 이전에 삽입된 문자열이 있으면 true 없으면 false를 반환한다.

문제 해결

• insert : 반복문을 통해 각 노드를 순차적으로 탐색하면서 문자열의 각 문자가 트라이에 존재하면 이어서 탐색을 진행하고, 없으면 각 문자를 추가하면서 진행한다. 탐색이 끝난 후 마지막 노드의 end 값을 true로 만들어 문자열의 끝이란 점을 명시한다.
• search : 반복문을 통해 각 노드를 순차적으로 탐색하면서 문자열의 각 문자가 트라이에서 이어지지 않으면 없는 경우이기 때문에 false를 반환한다. 이후에 모두 이어지면, 마지막 노드가 문자열의 끝인지를 판별하는 논리형 변수 end를 통해 문자열의 끝인지 확인하여 주어진 문자가 존재하는지 판단한다. 존재하면 true, 아니면 false를 반환한다.
• startsWith : 위의 search와 동일한 로직을 가지지만, 문자열의 끝인지의 여부를 판별하지 않도록하여 해당 문자열로 시작하는 문자열이 있는지 확인할 수 있도록 했다.

시간 복잡도

• insert : O(N) - N word 문자 길이
• search : O(N) - N은 word 문자 길이
• startsWith : O(N) - N은 prefix 문자 길이

풀이 코드

class Trie {
    public static class Node {
        Map<Character, Node> child;
        boolean end;

        public Node () {
            this.child = new HashMap<>();
            end = false;
        }
    }

    private Node root;

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

        for (char c : word.toCharArray()) {
            if (!now.child.containsKey(c)) {
                now.child.put(c, new Node());
            }
            now = now.child.get(c);
        }

        now.end = true;
    }
    
    public boolean search(String word) {
        Node now = this.root;

        for (char c : word.toCharArray()) {
            if (!now.child.containsKey(c)) {
                return false;
            }
            now = now.child.get(c);
        }
        return now.end;        
    }
    
    public boolean startsWith(String prefix) {
        Node now = this.root;

        for (char c : prefix.toCharArray()) {
            if (!now.child.containsKey(c)) {
                return false;
            }
            now = now.child.get(c);
        }

        return true;
    }
}

결과

시간	메모리
46 ms	55.9 MB