[LeetCode] 208. Implement Trie (Prefix Tree)

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

Implement Trie (Prefix Tree) - LeetCode

Try를 직접 구현하는 문제입니다.

 

트라이("try"로 발음) 또는 접두사 트리는 문자열 데이터 집합에서

키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다.

이 데이터 구조는 자동 완성 및 맞춤법 검사기 등 다양한 용도로 사용됩니다.

 

insert, search, startsWith 메서드를 구현해야 합니다.

 

 

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

 

문제접근

우선 Try를 사용하는 가장 큰 이유는 문자열을 검색하기 위해서입니다.

문자열을 효율적으로 검색하고, Try의 핵심기능인 startsWith기능을 최대한 효율적으로 하기위해 노력했습니다.

 

전체적인 틀

문자열의 각 알파벳마다 하나의 Node라고 생각하고 접근할 것입니다.

Node는 문자열의 마지막을 알리는 isEndOfWord 변수를 boolean값으로 포함하고있습니다.  

insert: 문자열 순서대로 Tree형식의 Node가 생성이 될것입니다.

search : Node를 재귀 탐색하다 isEndOfWord를 만나면 성공, null을 만나면 실패입니다.

startsWith : Node를 탐색하다 null을 만나면 false를반환합니다. 

 

저장 방법

문자열을 검색하기 위해 주어지는 문자열을 Charater단위로 쪼개서 Map의 Key로 저장할 것입니다.

Map으로 저장하는 Key값으로 조회시 O(1)의 시간복잡도를 갖고있기때문입니다.

Map의 경우 resizing을 고려해야하지만, LinkedList의 조회 O(n)보다 효율적이라 판단하여 Map을 선택하였습니다.

 

삽입, 탐색 방법

Try도 Tree기반입니다.

따라서 재귀형식으로 삽입,탐색을 할것입니다.

 

코드

Node

각 Charater마다 저장될 Node입니다.

Node마다 isEndOfWord라는 boolean을 갖고있어 해당 Node가 문자열의 마지막임을 나타냅니다.

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

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

Insert

word를 받아 재귀탐색을 합니다.

word의 길이가 0일때 해당 Node의 isEndOfWord를 true로 바꾸고 종료합니다.  

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

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

            final 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

해당 노드에 알파벳이 없다면 false입니다.

그게 아니라면 마지막 노드에서 isEndOfWord를 반환해 줍니다.

	public boolean search(String word) {
            return search(this.root, word);
        }

        private boolean search(final Node node, final String word) {
            if (word.length() == 0) {
                return node.isEndOfWord;
            }

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

            if (child == null) {
                return false;
            }

            return search(child, word.substring(1));
        }

StartsWith

만약 child가 null이라면 prefix가 없는것이니 false를 하고

반복문이 종료되면 prefix가 있다는 것이니 true를 반환합니다. 

 

반복문

        public boolean startsWith(String prefix) {
            Node currentNode = this.root;

            for (char c: prefix.toCharArray()) {
                Node child = currentNode.children.get(c);

                if (child == null) return false;

                currentNode = child;
            }
            return true;
        }

재귀

재귀적으로 탐색하다 word의 길이가 0이면 prefix가 전부 포함되었다는 뜻이므로 return true

만약 중간에 child가 null이라면 return false를 해주면 됩니다.

	public boolean startsWith(String prefix) {
            return startsWith(this.root, prefix);
        }

        private boolean startsWith(final Node node, final String word) {
            if (word.length() == 0) {
                return true;
            }

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

            if (child == null) {
                return false;
            }

            return startsWith(child, word.substring(1));
        }

전체코드

class Trie {
    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);
        }

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

            final 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) {
            return search(this.root, word);
        }

        private boolean search(final Node node, final String word) {
            if (word.length() == 0) {
                return node.isEndOfWord;
            }

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

            if (child == null) {
                return false;
            }

            return search(child, word.substring(1));
        }
    
    public boolean startsWith(String prefix) {
            Node currentNode = this.root;

            for (char c: prefix.toCharArray()) {
                Node child = currentNode.children.get(c);

                if (child == null) return false;

                currentNode = child;
            }
            return true;
        }
}

 

느낀점

Tree는 여러가지 형태로 자주 쓰이는것 같습니다.

Tree를 탐색할때 재귀를 많이 이용하게되니 재귀에대한 공부를 더 깊이있게 해야하것 같습니다.