[LeetCode] 211. Design Add and Search Words Data Structure - Java

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/

Design Add and Search Words Data Structure - LeetCode

---

문제

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 3 dots in word for search queries.
• At most 104 calls will be made to addWord and search.

---

풀이

풀이 과정

문제에서 주어진 조건에 따라 단어를 저장하고 단어를 찾아내는 사전 프로그램을 작성하는 문제이다.
바로 이전에 풀이했던 208. Implement Trie (Prefix Tree) 와 유사한 문제이다.

https://hyojun.tistory.com/entry/LeetCode-208-Implement-Trie-Prefix-Tree-Java-%EC%9E%91%EC%84%B1%EC%A4%91

[LeetCode] 208. Implement Trie (Prefix Tree) - Java

우선 객체를 생성하고 단어를 추가하는 과정은 Implement Trie를 구현하는 과정과 동일하다.

public class Node {
    // 현재 노드까지가 단어인지 아닌지 판단할 변수
    boolean isWord;
    // 현재 노드의 자식노드를 저장할 Map
    Map<Character, Node> children = new HashMap<>();
}

class WordDictionary {
    // 노드 변수 선언
    Node root;
    
    public WordDictionary() {
        // 새로운 루트 노드 생성
        root = new Node();
    }
    
    public void addWord(String word) {
        // 트리 최상위 노드
        Node node = root;

        // 문자열 끝까지 탐색
        for(int i = 0; i < word.length(); i++){
            // 현재 탐색중인 문자
            Character c = word.charAt(i);
            // 자식 노드에 현재 탐색중인 문자가 없는 경우
            if(!node.children.containsKey(c)){
                // 노드를 새로 생성하고 자식노드에 삽입
                node.children.put(c, new Node());
            } 

            // 노드를 갱신
            node = node.children.get(c);
            // 문자열을 끝까지 탐색한 경우 단어 여부 업데이트
            if(i == word.length() - 1){
                node.isWord = true;
            }
        }
    }

 

Implement Trie와 다른 점은 문자를 찾는 search 함수에서 문자가 알파벳이 아닌 '.' 이 주어질 수 있다는 점인데 '.'은 모든 알파벳에 대응될 수 있는 것으로 간주한다.

그렇기 때문에 '.'이 오는 경우 DFS를 통하여 모든 자식 노드들을 탐색해 볼수 있도록 search 함수만 약간의 수정을 해주도록 한다.

DFS 탐색을 할 수 있도록 함수를 하나 생성해주고 현재 탐색중인 노드와, 찾고자 하는 단어, 그리고 현재 탐색중인 인덱스를 파라미터로 전달한다.

 public boolean dfs(Node root, String word, int idx) {
 
 }

 

문자열을 끝까지 탐색한 경우 단어 여부에 따라 결과값을 return한다. 

// 문자열을 끝까지 탐색한 경우 단어 여부에 따라 결과값을 return
if(idx == word.length()) return root.isWord;

 

그 후 현재 탐색중인 문자에 따라 두 가지 경우로 나누어 탐색을 진행한다.
먼저 현재 탐색중인 문자가 '.'인 경우, 현재 노드의 자식노드들을 인덱스를 증가시키며 재귀탐색하여 true가 되는 경우가 존재한다면 true를 return한다.

// 현재 탐색중인 문자
Character c = word.charAt(idx);

// 현재 탐색중인 문자가 '.'인 경우
if(c == '.') {
    // 현재 노드의 자식노드들을 탐색하여 true가 되는 경우 true를 return
    for(Character key : root.children.keySet()) {
       if(dfs(root.children.get(key), word, idx + 1)) return true;
    }
}

 

다음으로 현재 탐색중인 문자가 알파벳인 경우, 자식노드에 현재 탐색중인 문자가 존재하는지 여부를 확인한다.
만약 현재 탐색중인 문자가 존재하지 않는다면 false를 return하고, 탐색중인 문자가 존재한다면 마찬가지로 인덱스를 증가시키며 자식노드를 탐색한다.

// 현재 탐색중인 문자가 알파벳인 경우
else {
    // 자식노드에 현재 탐색중인 문자가 존재하지 않는 경우 false를 return
    if(root.children.get(c) == null) return false;
    // 자식노드에 현재 탐색중인 문자가 존재하는 경우 다음 레벨을 탐색
    return dfs(root.children.get(c), word, idx + 1);
}

---

최종 코드

public class Node {
    // 현재 노드까지가 단어인지 아닌지 판단할 변수
    boolean isWord;
    // 현재 노드의 자식노드를 저장할 Map
    Map<Character, Node> children = new HashMap<>();
}

class WordDictionary {
    // 노드 변수 선언
    Node root;
    
    public WordDictionary() {
        // 새로운 루트 노드 생성
        root = new Node();
    }
    
    public void addWord(String word) {
        // 트리 최상위 노드
        Node node = root;

        // 문자열 끝까지 탐색
        for(int i = 0; i < word.length(); i++){
            // 현재 탐색중인 문자
            Character c = word.charAt(i);
            // 자식 노드에 현재 탐색중인 문자가 없는 경우
            if(!node.children.containsKey(c)){
                // 노드를 새로 생성하고 자식노드에 삽입
                node.children.put(c, new Node());
            } 

            // 노드를 갱신
            node = node.children.get(c);
            // 문자열을 끝까지 탐색한 경우 단어 여부 업데이트
            if(i == word.length() - 1){
                node.isWord = true;
            }
        }
    }
    
    public boolean search(String word) {
        return dfs(root, word, 0);
    }
    
    public boolean dfs(Node root, String word, int idx) {
        // 문자열을 끝까지 탐색한 경우 단어 여부에 따라 결과값을 return
        if(idx == word.length()) return root.isWord;
        
        // 현재 탐색중인 문자
        Character c = word.charAt(idx);
        
        // 현재 탐색중인 문자가 '.'인 경우
        if(c == '.') {
            // 현재 노드의 자식노드들을 탐색하여 true가 되는 경우 true를 return
            for(Character key : root.children.keySet()) {
               if(dfs(root.children.get(key), word, idx + 1)) return true;
            }
        }
        // 현재 탐색중인 문자가 알파벳인 경우
        else {
            // 자식노드에 현재 탐색중인 문자가 존재하지 않는 경우 false를 return
            if(root.children.get(c) == null) return false;
            // 자식노드에 현재 탐색중인 문자가 존재하는 경우 다음 레벨을 탐색
            return dfs(root.children.get(c), word, idx + 1);
        }
        
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

---