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

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

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

Trie에 단어를 저장하고, search를 하는 과정을 구현

그리고 search를 할 때 ' . ' 을 포함해서 찾게되면 ' . ' 은 모든 문자로 생각해서 일치하는 단어가 있는지 찾는 게 문제이다

 

Trie라는 자료구조를 처음 접하게 되어서 되게 신선했고, 문자열을 검색하는 방식이 독특해서 이 문제도 풀고 추후에 이론으로 한번 대충이라도 정리를 해볼 생각이다.

 

 

📌 -  풀이

1 ) Node - Map<Character, Node > map 구조와 끝을 표현하는 isEnd로 구성

 

2) 생성시 root = new Node() 초기화

 

3) addWord : root Node 부터 입력하고자 하는 단어를 한 문자씩 반복문을 사용하고, Node의 map안에 해당하는 문자가 없으면, 해당 하는 문자를 넣고 현재 노드를 방금 입력한 노드로 변경

 Node node = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i); // 한 글자씩
            if(!node.map.containsKey(c)) node.map.put(c,new Node()); // node안에 c문자가 없으면 map에 삽입하고
            node = node.map.get(c); // 현재노드를 방금 넣은 c문자의 노드로 변경
        }
        node.isEnd = true;

 

4) search : search의 경우 dfs 방식으로 완전탐색하면서 ' . ' 일경우와 아닐 경우를 나눠서 찾음

public boolean dfsSearch(Node p, String word, int start) {
		if (p.isEnd && start == word.length()) .
			return true;
 
		if (start >= word.length())
			return false;
 
		char c = word.charAt(start);
 
		if (c == '.') { // c가 '.'일 경우
			boolean tResult = false;
			for (char key : p.map.keySet()) { // p의 keySet을 반복문으로 돌면서
					if (dfsSearch(p.map.get(key), word, start + 1)) { // dfs로 한 단계씩 내려가면서 완전탐색
						tResult = true;
						break;
					}
			}
 
			if (tResult)
				return true;
		} else {
		
			if (p.map.get(c) != null) { // '.'이 아닐 때 
				return dfsSearch(p.map.get(c), word, start + 1);
			} else {
				return false;
			}
		}
 
		return false;
	}

 

 

🔥 - Java 전체 코드

class Node {
    Map<Character , Node > map;
    boolean isEnd;
    Node(){
        map = 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++){
            char c = word.charAt(i);
            if(!node.map.containsKey(c)) node.map.put(c,new Node());
            node = node.map.get(c);
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
       return dfsSearch(root, word, 0);  
    }

    public boolean dfsSearch(Node p, String word, int start) {
		if (p.isEnd && start == word.length())
			return true;
 
		if (start >= word.length())
			return false;
 
		char c = word.charAt(start);
 
		if (c == '.') {
			boolean tResult = false;
			for (char key : p.map.keySet()) {
					if (dfsSearch(p.map.get(key), word, start + 1)) {
						tResult = true;
						break;
					}
			}
 
			if (tResult)
				return true;
		} else {
			if (p.map.get(c) != null) {
				return dfsSearch(p.map.get(c), word, start + 1);
			} else {
				return false;
			}
		}
 
		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);
 */