Design Add and Search Words Data Structure - 리트코드

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

평가

풀이 시간 : 30분
결과 : 1회 실패 후 성공 (답안 참조하지 않았습니다)

예시를 통해 처음에 간과한 사실을 말씀드리겠습니다.
abc라는 문자열이 있다면 a->b->c 아래와 같은 방식으로 연결됩니다.
만약 ab라는 문자열을 검색하면 해당 문자열은 존재하지 않으므로 false를 반환해야 하는데, a->b라는 경로가 있으니 true를 반환해버리는 실수를 했습니다.

각 노드마다 isEnd 라는 플래그를 통해 해당되는 문자열이 나왔는지 검사하도록 만들었습니다.

아이디어

트라이 자료구조를 통해 풀 수 있습니다.
트라이를 구현하기 위해 Tree 형태를 사용했고, 각 노드는 26개의 자식(a-z)을 가질 수 있도록 배열을 추가했습니다.

이 문제의 특징으로는 wild card가 존재합니다. .이라는 문자가 나오면 모든 문자열을 의미합니다.
.가 나오면 for문을 돌려 26개의 모든 자식을 방문하도록 구현했습니다.

정답 코드

    class WordDictionary {
        WordDictionary[] store;
        boolean[] isEnd;

        public WordDictionary() {
            store = new WordDictionary[26]; // 0부터 25, 26개
            isEnd = new boolean[26];
        }

        public void addWord(String word) {

            int idx = word.charAt(0) - 'a';
            if (word.length() == 1) {
                isEnd[idx] = true;
                return;
            }

            if (store[idx] == null) {
                store[idx] = new WordDictionary();
            }
            store[idx].addWord(word.substring(1, word.length()));
        }

        public boolean search(String word) {
            if (word.length() == 0) {
                return true;
            }
            int idx = word.charAt(0) - 'a';
            if (word.length() == 1) {
                if (word.charAt(0) == '.') {
                    for(boolean each : isEnd) {
                        if (each) {
                            return true;
                        }
                    }
                    return false;
                }

                return isEnd[idx];
            }

            if (word.charAt(0) == '.') {
                for(int i=0; i<26; i++) {
                    WordDictionary child = store[i];
                    if (child != null) {
                        boolean result = child.search(word.substring(1,word.length()));
                        if (result) {
                            return true;
                        }
                    }
                }
                return false;
            }

            WordDictionary child = store[idx];
            if (child == null) {
                return false;
            }
            return child.search(word.substring(1,word.length()));
        }
    }