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

난이도 : medium

문제링크

• 단어 추가, 찾기의 기능을 가진 자료구조를 구현하라
  
  • 찾기 : '.' 문자 사용 가능 (와일드카드)
• word
  • 1 <= word.length <= 25
  • lowercase english letter

 

1. 접근법

• Trie 자료구조를 구현한다
• addWord : trie 자료구조와 동일
• search : . 와일드카드 기능 추가 필요 (trie 자료구조와 거의 동일)
  • word의 첫 글자가 '.'일 경우
    
    • node의 children 서브트리 전부를 search 검색을 하여, 각 서브트리에 한건이라도 만족하는 단어가 있다면 true
    • node의 children size가 0일 경우, 검색할 자식이 없으므로 false

2. 의사코드

private boolean search(Node node, String word) {
    if (word의 길이가 0이라면) {
    	word의 문자 하나하나를 따라 서브트리의 노드를 모두 방문하였음 
    	-> node.endOfWord 리턴
    }
    
    if (word의 첫글자가 '.'이라면) {
    	if (node의 자식이 없다면) {
        	검색할 자식이 없으므로, 
            -> return false
        }
        
        List tmp;
        for (entry : node.children.entrySet()) {
        	tmp.add(search(entry.getValue(), word.substring(1));
        }
        
		return !tmp.stream().allMatch(b -> b == false);        
    }
    
    return search(node.children.get(word의 첫번째 단어), word.substring(1));
}

 

 

3. 구현 코드

class WordDictionary {

    class Node {
        private Map<Character, Node> children;
        private boolean endOfWord;

        Node () {
            this.children = new HashMap<>();
            this.endOfWord = false;
        }
    }

    private Node root;
    
    public WordDictionary() {
        this.root = new Node();
    }
    
    public void addWord(String word) {
        this.addWord(this.root, word);
    }

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

        char c = word.charAt(0);
        Node child = node.children.get(c);
        if (child == null) {
            child = new Node();
            node.children.put(c, child);
        }

        addWord(child, word.substring(1));
    }
    
    public boolean search(String word) {
        return search(this.root, word);
    }

    private boolean search(Node node, String word) {
        if (word.length() == 0) {
            return node.endOfWord;
        }

        char c = word.charAt(0);
        Node child = null;
        if (c == '.') {            
            if (node.children.size() == 0) {                
                return false;
            }
            
            List<Boolean> tmp = new ArrayList<>();
            for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
                tmp.add(search(entry.getValue(), word.substring(1)));
            }

            return !tmp.stream().allMatch(b -> b == false);
        } 

        child = node.children.get(c);
        if (child == null) {
            return false;
        }

        return search(child, word.substring(1));
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(n) - 모든 노드를 생성해야 함

 

5. 개선점

• 잘 모르겠다. 

 

6. 회고

• 다른 풀이를 보아도 비슷하게 풀었다