[LeetCode] 211. Design Add and Search Words Data Structure[재도전중]

Design Add and Search Words Data Structure - LeetCode

새 단어를 추가하고 이전에 추가한 문자열과 일치하는 문자열을 찾는 것을 지원하는 데이터 구조를 설계합니다.

단어는 점 '.'을 포함할 수 있으며, 여기서 점은 어떤 문자와도 일치할 수 있습니다

 

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

문제 접근

기본적으로 전에 풀어던 try문제와 비슷하게 접근하였습니다.

try에 대한 이해가 없다면 아래글을 먼저 보고오셔야 이번 포스팅을 이해하기 쉬울것입니다.   

[LeetCode] 208. Implement Trie (Prefix Tree)

 

하지만, 문제가있었습니다.

바로 '.' 이였습니다.

그래서 add를 할때 children Node에 '.'을 key로 모든 알파벳을 넣으면 되겠다고 생각하였습니다.

        public void addWord(String word) {
            addWord(this.root, word);
        }

        private void addWord(final Node node, final String word) {
            if (word.length() == 0) {
                node.isEndOfWord = true;
                return;
            }

            final char c = word.charAt(0);
            Node child = node.children.get(c);

            if (child == null) {
                child = new Node();
                node.children.put(c, child);
                node.children.put('.', child);
            }

            addWord(child, word.substring(1));
        }

하지만 문제는 key값으로 '.'를 넣을때마다 list형식으로 추가되는게 아니라, 값을 갱신하기때문에

마지막에 들어간 '.'만 들어가서 실패하였습니다.

 

기본 TestCase는 통과하였지만, 역시 실제 정답을 받지는 못했습니다.

 

다른 사람의 풀이

해결방법을 찾지 못하여 검색을 통해 정답을 확인하였습니다.