Design Add and Search Words Data Structure

요구사항 정리

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

클래스를 구현합니다 WordDictionary.

WordDictionary() 개체를 초기화합니다.
void addWord(word)word데이터 구조에 추가되며 나중에 일치시킬 수 있습니다.
bool search(word) 데이터 구조에 일치 true하는 문자열이 있는지 여부를 반환합니다 . 점은 어떤 문자와도 일치할 수 있는 점을 포함할 수 있습니다 .wordfalseword'.'

풀이

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

public class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    private boolean searchHelper(String word, TrieNode node) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                // '.' (와일드카드)를 처리하기 위해 모든 가능한 자식 노드를 재귀적으로 검색합니다.
                for (TrieNode child : node.children.values()) {
                    if (searchHelper(word.substring(i + 1), child)) {
                        return true;
                    }
                }
                return false;
            } else if (node.children.containsKey(c)) {
                node = node.children.get(c);
            } else {
                return false;
            }
        }
        return node.isEndOfWord;
    }

    public boolean search(String word) {
        return searchHelper(word, root);
    }
}