208. Implement Trie (Prefix Tree)

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

문제

trie 클래스를 구현하자

• Trie(): 객체 초기화
• void insert(String word): 문자열 삽입
• boolean search(String word): 문자열이 trie에 있는지 확인
• boolean startsWith(String prefix): 접두사를 가진 이전에 삽입된 문자열 단어가 있는지 확인

나의 풀이

아래와 같이 코드를 짰지만, 일부 함수가 자꾸 true가 나오지 않고, false가 나와서 고쳤다.

class Trie {

    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        insert(root, word);
    }
    
    public boolean search(String word) {
        return search(root, word);
    }
    
    public boolean startsWith(String prefix) {
        return startsWith(root, prefix);
    }

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

        char c = word.charAt(0);
        Node node = root.children.get(c);
        
        if (node == null) {
            node = new Node();
            root.children.put(c, node);
        }

        insert(node, word.substring(1));
    }
    
    public boolean search(Node root, String word) {
        if (word.length() == 0) {
            return root == null;
        }

        char c = word.charAt(0);
        Node node = root.children.get(c);
        if (node == null)
            return false;

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

    public boolean startsWith(Node root, String word) {
        if (word.length() == 0) {
            return root.children.size() > 0;
        }

        char c = word.charAt(0);
        Node node = root.children.get(c);
        if (node == null)
            return false;

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

    class Node {
        Map<Character, Node> children = new HashMap();
    }
}

다른 풀이

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        root.insert(word, 0);
    }
    
    public boolean search(String word) {
        return root.search(word, 0);
    }
    
    public boolean startsWith(String prefix) {
        return root.startsWith(prefix, 0);
    }

    class Node {
        Node[] nodes;
        boolean isEnd;

        Node() {
            nodes = new Node[26];
        }

        private void insert(String word, int idx) {
            if (idx >= word.length()) return;
            int i = word.charAt(idx) - 'a';
            if (nodes[i] == null) {
                nodes[i] = new Node();
            }

            if (idx == word.length()-1) nodes[i].isEnd = true;
            nodes[i].insert(word, idx+1);
        }

        private boolean search(String word, int idx) {
            if (idx >= word.length()) return false;
            Node node = nodes[word.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == word.length() - 1 && node.isEnd) return true;

            return node.search(word, idx+1);

        }

        private boolean startsWith(String prefix, int idx) {
            if (idx >= prefix.length()) return false;
            Node node = nodes[prefix.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == prefix.length() - 1) return true;

            return node.startsWith(prefix, idx+1);
        }
    }
}

클래스 Node에 직접 필요한 함수를 구현했고, Node의 child 노드에 대해, 알파벳 수만큼의 배열을 생성해 이용한다는 점이 달랐다.