[ Top Interview 150 ] 211. Design Add and Search Words Data Structure

문제

211. Design Add and Search Words Data Structure

 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.

알고리즘 전략

• 기본 전략

  • 문자열을 저장하고 빠르게 찾을 수 있는 자료 구조가 필요함
  • 동적 Array를 이용한다면 현재 저장한 자료를 전부 탐색해야 한다.
  • 이전 문제에서 사용한 Trie를 이용한다면 찾고자 하는 문자의 길이에 비례하여 시간이 걸린다.
    • 이는 저장되어 있는 자료 개수와 상관없는 시간 복잡도를 갖는다.

• Trie 구현

  • 이전 문제의 코드를 유사하게 이용하여 이용한다.
  • void addWord(word)
    • 맨 앞글자를 알파벳 순서를 index로 하고 나머지 글자를 통해 만든 Trie를 value로 하는 Array을 이용
    • 해당 인덱스 자리가 null이 아니라면, 재귀적으로 insert(substring)을 하고, null이라면 새로 만들어서 넣은 후에 재귀적으로 insert(substring)을 요청한다.
    • substring : word에서 맨 앞글자를 제거한 string
  • bool search(word)
    • Map에 word의 맨 앞글자를 key로 하는 값을 요청한다.
      • 해당 값이 없다면, false를 반환
    • 재귀적으로 search(String substring)를 요청하도록 함
      • substring의 길이가 0인 경우, 해당 문자로 끝나는지 확인함 (isEnd)
    • 맨 앞글자가 .인 경우, 모든 하위 Node를 search(substring)을 한다.

정답 코드

class WordDictionary {
    
    private final Trie trie = new Trie();

    public WordDictionary() {
    }

    public void addWord(String word) {
        trie.insert(word);
    }

    public boolean search(String word) {
        return trie.search(word);
    }

    class Trie {

        private static final int COUNT_OF_LETTERS = 26;
        private static final char START_LETTER = 'a';
        private static final char ALL_LETTER = '.';

        private final Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[COUNT_OF_LETTERS];
            isEnd = false;
        }

        public void insert(String word) {
            if (word.length() == 0) {
                isEnd = true;
                return;
            }

            Trie child = getChild(word);
            if (child == null) {
                child = putNewChild(word);
            }
            child.insert(word.substring(1));
        }

        public boolean search(String word) {
            if (word.length() == 0) {
                return isEnd;
            }
            
            if (word.charAt(0) != ALL_LETTER) {
                Trie child = getChild(word);
                return child != null && child.search(word.substring(1));
            }
            
            for (Trie child : children) {
                if (child != null && child.search(word.substring(1))) {
                    return true;
                }
            }
            return false;
        }

        private Trie getChild(String word) {
            char key = word.charAt(0);
            return children[key - START_LETTER];
        }

        private Trie putNewChild(String word) {
            char key = word.charAt(0);
            Trie child = new Trie();
            children[key - START_LETTER] = child;
            return child;
        }
    }
}