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

208. Implement Trie (Prefix Tree)

⭐ 문제

Trie 클래스를 구현하세요

Trie() - Trie 객체를 초기화
void insert(String word) - 문자열 word를 Trie에 삽입
boolean search(String word) - 문자열 word가 Trie에 있는 경우 true를 반환하고, 그렇지 않으면 false를 반환
boolean startsWith(String prefix) - 이전에 삽입된 문자열 중에서 접두사 prefix를 가진 문자열이 있는 경우 true를 반환하고, 그렇지 않으면 false를 반환

🤔 접근 방향

Trie 클래스 내에 TrieNode 클래스를 내장하여 Trie 데이터 구조를 구현합니다. TrieNode 클래스는 노드의 자식 노드 배열과 문자열의 끝을 나타내는 플래그를 포함합니다. 이 클래스를 사용하여 문자열 삽입, 문자열 검색 및 접두사 검색 기능을 구현합니다.

✍️ 의사 코드

1. TrieNode 클래스를 내장하여 Trie 클래스를 정의합니다. Trie 클래스는 root 노드를 가지며, TrieNode 클래스는 노드의 자식 노드 배열과 문자열의 끝을 나타내는 플래그를 갖습니다.
2. 문자열을 Trie에 삽입하는 insert 메서드를 구현합니다.
   2.1 문자열을 문자 단위로 순회하면서 각 문자를 Trie에 추가합니다.
   2.2 문자가 Trie에 없는 경우, 새로운 TrieNode를 생성하여 자식 노드로 추가합니다.
   2.3 문자열의 끝에 도달하면 해당 노드의 isEndOfWord 플래그를 true로 설정합니다.
3. 문자열을 Trie에서 검색하는 search 메서드를 구현합니다.
   3.1 문자열을 문자 단위로 순회하면서 각 문자를 Trie에서 찾습니다.
   3.2 만약 중간에 누락된 문자가 있다면 검색 실패로 처리합니다.
   3.3 문자열의 끝에 도달하고 해당 노드의 isEndOfWord 플래그가 true인 경우 검색 성공으로 처리합니다.
4. 접두사를 Trie에서 검색하는 startsWith 메서드를 구현합니다.
   4.1 접두사를 문자 단위로 순회하면서 각 문자를 Trie에서 찾습니다.
   4.2 만약 중간에 누락된 문자가 있다면 접두사가 존재하지 않는 것으로 처리합니다.
   4.3 접두사의 끝에 도달하면 검색 성공으로 처리합니다.
5. Trie 클래스를 사용하여 문자열 삽입, 검색, 접두사 검색을 수행합니다.

✅ 나의 풀이

class Trie {

    private class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26]; // Assuming lowercase English alphabet characters
            isEndOfWord = false;
        }
    }

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

🖥️ 결과

Runtime: 34 ms
Memory Usage: 54.7 MB