https://leetcode.com/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150

211. Design Add and Search Words Data Structure

⭐ 문제

새로운 단어를 추가하고 이전에 추가된 문자열과 일치하는지 확인하는 데이터 구조를 설계하세요

WordDictionary 클래스를 구현하세요:

WordDictionary() 객체를 초기화
void addWord(word) 단어를 데이터 구조에 추가하며 나중에 일치시킬 수 있음
bool search(word) 데이터 구조에 일치하는 문자열이 있는 경우 true를 반환하거나 그렇지 않은 경우 false를 반환. (단어에는 점 '.'이 포함될 수 있으며, 점은 어떤 문자와도 일치할 수 있음)

🤔 접근 방향

• WordDictionary() : 생성자에서 Trie 자료구조를 초기화하고, Trie의 루트 노드를 설정할 것입니다. 이렇게 하면 WordDictionary 객체가 생성될 때마다 새로운 Trie가 생성되고 초기화됩니다.
• addWord(word) : 이 메서드는 주어진 단어를 데이터 구조에 추가하는 역할을 합니다. Trie를 사용하여 주어진 단어의 각 문자를 순서대로 Trie에 추가합니다. 문자를 추가할 때, 이미 Trie에 있는 문자는 기존 노드로 이동하고, 존재하지 않는 문자는 새로운 노드를 생성하여 Trie에 추가합니다.
• search(word) : 주어진 단어가 데이터 구조에 있는지 검색하는 역할을 합니다. Trie를 루트부터 시작하여 주어진 단어의 각 문자를 검색합니다. 또한 문자가 '.'인 경우, 모든 자식 노드를 검색하여 와일드카드 문자를 처리합니다. 문자가 일반 알파벳인 경우, 해당 문자 노드로 이동하여 검색을 진행합니다. 단어의 끝에 도달하면 해당 노드가 단어의 끝을 나타내는지 확인하여 결과를 반환합니다.

✍️ 의사 코드

클래스 WordDictionary {
    클래스 TrieNode {
        자식 노드 배열
        노드가 단어의 끝인지 나타내는 플래그

        생성자 :
            배열 초기화
            단어의 끝을 false로 초기화
    }

    Trie의 루트 노드

    생성자:
        root를 새로운 TrieNode로 초기화

    메서드 addWord(word):
        현재 노드를 root로 설정
        각 문자를 word에서 가져와서 반복:
            문자를 인덱스로 변환
            현재 노드의 해당하는 자식 노드가 null이면:
                새로운 TrieNode를 생성하여 해당하는 자식 노드에 할당
            현재 노드를 해당하는 자식 노드로 업데이트
        현재 노드의 단어의 끝을 true로 설정

    메서드 search(word):
        검색할 단어를 찾기 위해 현재 노드를 root로 설정
        각 문자를 word에서 가져와서 반복:
            문자가 '.'인 경우:
                모든 자식 노드를 순회하며 재귀적으로 검색:
                    검색 결과가 true인 경우:
                        true를 반환
                모든 자식 노드를 검색해도 일치하는 단어를 찾지 못한 경우:
                    false를 반환
            문자가 일반 알파벳 문자인 경우:
                현재 노드의 해당하는 자식 노드로 이동
                만약 해당하는 자식 노드가 null인 경우:
                    false를 반환
        현재 노드의 단어의 끝이 true이면:
            true를 반환
        그렇지 않으면:
            false를 반환

✅ 나의 풀이

class WordDictionary {
    private class TrieNode {
        private TrieNode[] children;
        private boolean isEndOfWord;
        
        public TrieNode() {
            children = new TrieNode[26];
            isEndOfWord = false;
        }
    }
    
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        return searchInNode(word, root);
    }
    
    private boolean searchInNode(String word, TrieNode node) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                for (TrieNode child : node.children) {
                    if (child != null && searchInNode(word.substring(i + 1), child)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (node.children[c - 'a'] == null) {
                    return false;
                }
                node = node.children[c - 'a'];
            }
        }
        return node.isEndOfWord;
    }
}

🖥️ 결과

Runtime: 217 ms
Memory Usage: 92.8 MB