꿀잠

문자열을 검색하는 커스텀 클래스를 만드는 문제이다.
Trie 자료구조를 이용해서 문제를 해결할 수 있다. Trie 자료구조란 문자열을 저장할 때 각 노드에 대한 자식 노드를 포인트 배열로 저장하는 형식이다.

해당 문제에선 "." 일 경우 검색 시 모든 문자가 가능하다는 조건이 있고 해당 부분이 문제의 핵심 부분이다. 조건문을 이용하여 해당 부분을 분기 처리하여 해결하였다. 노드를 List 형식으로 하여 순회하였으며, "." 일 경우 연결되는 모든 노드를 List에 전부 추가하여 주었다.

모든 순회가 끝난 이후 마지막 노드들 중 isLast가 있을 경우 검색이 성공한 것이므로 True를 반환하였다. 만약 최종 순회 후 List가 비어있을 경우 result의 초기 값인 false가 반환되며 이는 주어진 문자열에 알맞게 마지막까지 이어지는 글자가 없는 것을 의미한다.

import java.util.*;  
  
class WordDictionary {  
  
    WordNode root;  
  
    public WordDictionary() {  
        this.root = new WordNode();  
    }  
  
    public void addWord(String word) {  
  
        WordNode before = this.root;  
  
        for(int i = 0; i < word.length(); i++){  
            int cur = word.charAt(i) - 'a';  
  
            if(before.next[cur] == null){  
                before.next[cur] = new WordNode();  
            }  
  
            before = before.next[cur];  
        }  
  
        before.isLast = true;  
    }  
  
    public boolean search(String word) {  
        List<WordNode> beforeList = new ArrayList<>();  
        WordNode start = this.root;  
        beforeList.add(start);  
        boolean result = false;  
        for(int i = 0; i < word.length(); i++){  
            char cur = word.charAt(i);  
            List<WordNode> nextList = new ArrayList<>();  
  
            for(WordNode before : beforeList){  
                if(cur == '.'){  
                    for(int j = 0; j < 26; j++){  
                        WordNode next = before.next[j];  
                        if(next != null){  
                            nextList.add(next);  
                        }  
                    }  
                }else{  
                    WordNode next = before.next[cur - 'a'];  
                    if(next != null){  
                        nextList.add(next);  
                    }  
                }  
  
            }  
            beforeList = nextList;  
        }  
  
        for(WordNode next: beforeList){  
            result = result || next.isLast;  
        }  
  
        return result;  
    }  
  
    private static class WordNode{  
        WordNode[] next;  
        boolean isLast;  
  
        WordNode(){  
            this.next = new WordNode[26];  
            isLast = false;  
        }  
    }  
}  
  
/**  
 * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */