211. Design Add and Search Words Data Structure java 풀이

이거는 앞의 문제 https://hello-backend.tistory.com/423 이거를 풀었으면 매우 쉽다.

그냥 저장은 똑같고, DFS 찾을 때에 . 이면 거기 싹다 찾으면 된다.

 

class Word {
    boolean isEnd;
    Word[] word = new Word[26];
}

class WordDictionary {
    Word root;

    public WordDictionary() {
        root = new Word();
    }

    // 객체가 객체를 저장하는 형태
        // 결국 특정 알파뱃에 대하여 그 아래에 객체가 존재하고 ... -> 반복 시 모든 문자열의 형태가 저장된다.
    // 그렇다면 어떻게 확인할 수 있을까?
        // DFS 를 통해 확인할 문자열을 하나씩 비교
            //  . 같은 것들은 어떻게 할 수 있을까?
                // 그냥 무조건 TRUE 로 두고 비교하면 된다.
    
    public void addWord(String word) {
        Word now = root;

        for(int i=0; i<word.length(); i++) {
            // 존재하는 객체가 없다는 것은 거기 저장된 문자가 없다는 것.
            if(now.word[word.charAt(i) - 'a'] == null) {
                // 저장해주면 된다.
                Word save = new Word();
                now.word[word.charAt(i) - 'a'] = save;
            }
            // 그리고 그 아래 문자열을 하나씩 비교해주면 된다.
            now = now.word[word.charAt(i) - 'a'];
        }
        // 끝까지 저장했으면 그곳이 마지막이 된다.
        now.isEnd = true;
    }
    
    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int index, Word now) {
        if(index == word.length()) {
            // 해당 문자를 다 비교했을 경우 그게 마지막이면 된다.
            return now.isEnd;
        }

        // . 이면 뭐든지 다올수 있는것인데
        if(word.charAt(index) == '.') {
            for(int i=0; i<26; i++) {
                // 그러면 이 노드에서 값이 있는 것들은 싹다 다음 DFS 를 돌리게 한다.
                if(now.word[i] != null) {
                    // 근데 이중 하나만 true 여도 얘는 true 가 된다.
                    if(dfs(word, index+1, now.word[i])) return true;
                }
            }
        } else {
            if(now.word[word.charAt(index) - 'a'] != null) {
                now = now.word[word.charAt(index) - 'a'];
                return dfs(word, index+1, now);
            } 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);
 */