[알고리즘] LeetCode - Design Add and Search Words Data Structure

Design Add and Search Words Data Structure - LeetCode

문제 설명

• 새로운 단어를 추가하고 문자열이 이전에 추가된 문자열과 일치하는지 찾는 클래스를 설계 구현해야 한다.
• 문자열의 일치 여부를 판단하는데에는 와일드 카드를 사용할 수 있다. 
• 와일드 카드는 '.' 으로 여기에는 모든 알파벳이 올 수 있다.
• 알파벳은 영문 소문자로만 구성된다.
• 작성해야할 클래스 구현체는 아래와 같다.
  • void addWord(String word) : 문자열을 추가한다.
  • boolean search(String word) : 저장된 문자열이 있으면 true 없으면 false를 반환한다.

문제 해결

• addWord : 트라이 구조를 통해 문자열을 문자로 쪼개어 노드로 생성하여 저장한다.
• search : 재귀를 통해서 트라이 구조를 탐색한다. 만약 문자가 '.' 이라면 현재 노드에 연결된 모든 문자 노드를 탐색하는 재귀 탐색을 수행하고, '.' 이 아니라면 해당 문자에 대한 탐색만을 진행한다. 이후 탐색이 끝까지 도달했을 때 주어진 문자열 word를 끝까지 탐색할 수 있으면 true, 끝까지 탐색할 수 없는 경우 false를 반환할 수 있도록 했다.

시간 복잡도

• addWord : O(N) - N은 word 문자열의 길이
• search : O(N) - N은 저장된 문자의 갯수 (트라이 구조에서 노드의 갯수)

풀이 코드

class WordDictionary {
    public static class Node {
        Node[] child;
        boolean end;

        public Node() {
            child = new Node[26];
            end = false;
        }
    }

    private Node root;

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

        for (char c : word.toCharArray()) {
            int i = c-'a';
            if (now.child[i] == null) {
                now.child[i] = new Node();
            }
            now = now.child[i];
        }

        now.end = true;
    }
    
    public boolean search(String word) {
        return search(this.root, word, word.length());     
    }

    private boolean search(Node node, String word, int size) {
        if (node == null) {
            return false;            
        }
        if (size == 0) {
            return node.end;
        }

        int i = word.charAt(0)-'a';

        if (word.charAt(0) == '.') {
            boolean flag = false;
            for (i = 0; i < 26; i++) {
                if (flag) break;
                if (node.child[i] == null) continue;
                flag = search(node.child[i], word.substring(1), size - 1);
            }
            return flag;
        } else {
            return search(node.child[i], word.substring(1), size - 1);
        }
    }
}

결과

시간	메모리
220 ms	92.5 MB