[Leetcode 211] - Design Add and Search Words Data Structure w/ Python

 

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.

 

 

 

 

새로운 단어를 추가하거나 기존에 추가한 단어가 들어가 있는지 확인하는 자료 구조를 만들어야 되는 문제

 

● WordDictionary(): 구조 생성

● void addWord(word): 구조에 단어를 추가

● bool search(word): 단어가 구조에 있으면 True, 아니라면 False 리턴

※ 중간에 "."이 발견되면 이는 어떤 글자든 상관 없는 뜻. 즉 모든 "."에 해당하는 자리에 어떤 글자가 되어도 상관 없다 

 

 

 

 

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

 

 

 

---

 

 

 

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

 

 

 

---

 

 

 

https://zenu.tistory.com/27

[Leetcode 208] - Implement Trie (Prefix Tree) w/ Python

 

 

Leetcode 208이랑 비슷하게 각 글자마다 노드를 늘려 단어를 추가하고 확인하는 방법을 사용했다

208이랑 다르게 DFS가 아닌 Backtrack으로 알고리즘을 해서 "." 컨디션들을 만족시켰다

 

 

---

 

 

백트래킹 설명:

※ 이미 추가할 글자가 다 구조에 들어가 있다고 가정

1. 현재 글자가 구조에 있다면 Index를 1 더해 다음 글자를 확인

2. 글자가 "."이라면 글자 자리에 있는 character들을 for loop으로 확인한뒤 인덱스 1 추가해 다 확인

3. "*"가 저장된 끝지점이라고 한다면 마지막 글자에 도달했을때 구조안에 "*"이 포함 되어 있어야된다

- 포함 되어 있다면 True, 아니라면 False

- "*"에 미리 도달했다면 False

- 글자가 구조에 없다면 False

4. 모든 컨디션이 통과되면 True라고 리턴

 

 

class WordDictionary:
    def __init__(self):
        self.trie = {}    

    def addWord(self, word: str) -> None:
        trie = self.trie # 구조 생성
        for char in word: # 글자마다
            if char not in trie: # 구조에 없다면 추가
                trie[char] = {}
            trie = trie[char] # 다음 글자로 넘어가서
        trie['*'] = None # 단어가 끝날때 "*"을 추가해 끝이라고 표시

    def search(self, word: str) -> bool:
        def backtrack(trie, i):
            if i == len(word):
                return '*' in trie
            
            if word[i] == '.':
                for key in trie:
                    if key != '*':                    
                        if backtrack(trie[key], i+1):
                            return True
                return False

            
            if word[i] not in trie:
                return False
            
            return backtrack(trie[word[i]], i+1)
        
        return backtrack(self.trie, 0)