[Leetcode] 211. Design Add and Search Words Data Structure

 

Identifying the Problem

Trie 구조, addword, search 기능을 구현한다.

단 search 기능에서 단어 중간에 '.' 이 있는 경우 pass하고 다음 글자로 넘어간다.

 

Example:

wordDictionary.addWord("bad");

wordDictionary.search(".ad"); 

return True

Organizing thoughts

Trie 와 addword는 208번 문제의 코드를 그대로 사용하고, search 부분을 정답코드 참고하였음.

 

[Leetcode] 208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/design-add-and-search-words-data-structure/discuss/774271/C%2B%2B-oror-Trie-Solution-oror-264-ms-Solution

Sourcecode

class TrieNode 
{
public:
    // TrieNode 객체 생성
    bool finish; //글자의 끝의 유/무 를 finish로 설정
    TrieNode *children[26]; //26개의 자식 노드 생성 ('a~z')
    
    TrieNode() //각 노드의 초기값 설정
    { 
        finish = false;  
        
        for (int i = 0; i < 26; i++)
            children[i] = NULL;
    }//처음 아무것도 없는 상태이므로 각 노드의 끝을 false와 NULL로 설정
};


class WordDictionary {
public:
    WordDictionary() 
    {
        root = new TrieNode(); //Trie 생성    
    }
    
    void addWord(string word) 
    {
        int word_len = word.length(); //단어의 길이
        int k = 0; //string -> int 알파벳 a~z 를 index로 사용하고자 k = 0~25 로 선언
        TrieNode *cur = root; //탐색노드 cur에 초기 TrieNode 대입
        
        for (int i = 0; i < word_len; i++) //단어의 한 글자씩 Trie 에 추가
        {
            k = word[i] - 'a';
            
            if (cur->children[k] == NULL) 
            {
                cur->children[k] = new TrieNode();
            }////해당 trie가 아무것도 없는 상태라면, 새로 하위 노드 생성
            
            cur = cur->children[k]; //다음 node로 이동
        }
        
        cur->finish = true; //단어의 끝 finish 값을 true로 설정 
        
    }
    
    bool search(string word) 
    {
        return searchHelper(word, root); //parameter를 수정한 search 함수
    }
        

    
private:
    TrieNode* root; //root 생성
    
    bool searchHelper(string word, TrieNode* current) 
    {
        for(int i = 0; i < word.size(); i++)
        {
            if(word[i] != '.'){ //기존 search 방식과 동일
                if(!current->children[word[i] - 'a']) 
                    return false;
                current = current->children[word[i] - 'a'];
            }
            else
            { // '.'이 단어 중간에 있는 경우
                for(int j = 0; j < 26; j++) // 다음 자식 노드 26개 모두를 탐색
                {
                    if(current->children[j] && searchHelper(word.substr(i + 1), current->children[j]))
                    { //다음 자식노드가 존재하고, 이후 다음 글자들이 Trie에 있는지 재귀로 탐색
                        return true; //하나라도 만족하면 true리턴
                    }
                }
                return false;
            }
        }
        return current->finish; //'.'이 없는 경우 단어의 끝에 해당하는 Trie->finish 값 리턴
    }
};