力扣面试150题--添加与搜索单词 - 数据结构设计

Day 68

题目描述

思路

根据昨天的trie前缀树进行修改，特殊需要考虑的点在于存在通配符，我来说明下如何解决这个问题的：
关键在于这段代码

 for (WordDictionary child : words.child) {
                if (child != null && find(child, word, i + 1)) {
                    return true;
                }
            }
            return false;

遍历当前节点的所有非空子节点，对每个子节点递归调用 find 函数，处理剩余字符（start + 1）。
只要找到一条有效路径，立即返回 true。
如果所有子节点都无法匹配，返回 false。
做法

class WordDictionary {
    public WordDictionary[]child;
    public boolean isend;
    public WordDictionary() {
        child=new WordDictionary[27];
        isend=false;
    }
    
    public void addWord(String word) {
        WordDictionary words=this;
        for(int i=0;i<word.length();i++){
            char x=word.charAt(i);
            int index=x-'a';
            if(words.child[index]==null){
                words.child[index]=new WordDictionary();
            }
            words=words.child[index];
        }
        words.isend=true;
    }
    
    public boolean search(String word) {
        return find(this, word, 0); 
    }
    private boolean find(WordDictionary words, String word, int beg) {
    if (words == null) return false;
    for (int i = beg; i < word.length(); i++) {
        char c = word.charAt(i);
        if (c == '.') {
            for (WordDictionary child : words.child) {
                if (child != null && find(child, word, i + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            int index = c - 'a';
            words =words.child[index];
            if (words == null) return false;
        }
    }
    return words.isend; // 检查最终节点是否为单词结尾
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */