[LeetCode/Top Interview 150] [Trie] 211. Design Add and Search Words Data Structure

문제 링크: https://leetcode.com/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"][],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 10^4 calls will be made to addWord and search.

전략:

거의 직전 문제인 트라이 구현과 동일하지만, 와일드카드 문자 '.' 을 사용한 검색이 추가됨
'.' 은 한 문자열에 최대 2번 나타날 수 있음.

내부에 Node 클래스를 구현하여 char 자료형의 형태로 알파벳을 저장하고, 이번에는 char[]으로 다음 노드를 참조하는 방식으로 구현하며, 검색시 현재 문자가 '.' 인 경우 모든 하위 노드를 검색한다.
Queue 또는 재귀로 구현해야 와일드 카드 검색에서 문제가 없을 듯 하다.
-> 재귀로 구현

코드 구현:

class WordDictionary {
    Node head;
    Node dummy = new Node();

    class Node {
        Node[] children;
        boolean end;

        Node() {
            this.children = new Node[26];
            this.end = false;
        }
    }

    public WordDictionary() {
        head = dummy;        
    }
    
    public void addWord(String word) {
        Node next = head;
        for (int i=0;i<word.length();i++) {
            int pos = word.charAt(i)-'a';
            if (next.children[pos] == null) {
                next.children[pos] = new Node();
            }
            next = next.children[pos];
        }
        next.end = true;
    }

    public boolean search(String word) {
        return searchDFS(word, 0, head);
    }
    
    public boolean searchDFS(String word, int index, Node next) {
        if (index == word.length()) { return next.end; }            
        char now = word.charAt(index);
        if (now == '.') { // 와일드 카드라면
            for (int i=0;i<26;i++) { // 소문자 26개
                // 리프 노드가 아니고 && 다음 노드 재귀로 검색한 결과가 false 가 아니라면
                if (next.children[i] != null && searchDFS(word, index+1, next.children[i])) {
                    return true;
                }
            }
            return false; // 모든 알파벳을 체크했는데 true가 없으면 false
        } else { // 와일드 카드가 아니라면
            if (next.children[now-'a'] == null) { return false; } // 이 문자가 없으면 false
            return searchDFS(word, index+1, next.children[now-'a']); // 이 문자가 있으면 재귀 호출
        }
    }
}

Time: 158 ms (88.91%), Space: 96.6 MB (68.33%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0211-design-add-and-search-words-data-structure/0211-design-add-and-search-words-data-structure.java

개선 방안:

개선이라기 보다는 Queue로도 구현 가능하지 않을까 싶다.
다만 재귀로 구현하는 것보다는 조건을 정하기 어려울 듯.

Solutions 탭의 타인 코드:

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

    /** Initialize your data structure here. */
    public WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    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.isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        TrieNode node = root;
        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(node);
        int level = 0;
        while (!queue.isEmpty() && level <= word.length()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TrieNode current = queue.poll();
                
                if (level == word.length()) {
                    if (current.isWord) {
                        return true;
                    } else {
                        continue;
                    }
                }
                
                char c = word.charAt(level);
                
                if (c == '.') {
                    for (TrieNode t : current.children) {
                        if (t != null) {
                            queue.offer(t);
                        }
                    }
                } else if (current.children[c - 'a'] != null) {
                    queue.offer(current.children[c - 'a']);
                }
            }
            level++;
        }
        return false;
    }
}
Time: 269 ms (32.16%), Space: 97.7 MB (57.76%) - LeetHub

회고:

처음에는 이전 문제의 응용이라고만 생각해서 조금 더 빨리 풀 수 있지 않을까 했었는데, 와일드 카드 문자를 통한 검색이라는 것 만으로도 생각보다 더 많은 부분을 고민할 수 밖에 없었다.
Queue를 통해 BFS로 문제를 해결하기 위해서 한참 고민했었는데 재귀로 하니 금새 답이 나왔던 것 같다.