阿狗工具

旦选准自己要走的道路，就勇敢地走下去，再难也要坚持，再远也不要放弃。一分耕耘未必有一分收获，但九分耕耘一定会有一分收获！天道酬勤！越努力，越幸运！

LC每日一题，参考1032.stream-of-characters，难度分1970。

题目

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

• StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
• boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

解题思路

• 因为查询字符流是追加倒序开始，所以考虑构造反向单词字典树进行搜索

反向构造字典树 57ms

class StreamChecker {

    //考虑字典树try trie
    class Trie {
        boolean isWord;
        Trie[] children = new Trie[26];//都是小写字母所以长度固定26
    }

    Trie trie;
    int maxWordLen = 0;//单词最大长度
    public StreamChecker(String[] words) {
        trie = new Trie();
        //构造字典树 查询后缀考虑反向从尾开始
        for(String value : words) {
            maxWordLen = Math.max(maxWordLen,value.length());
            char[] word = value.toCharArray();
            Trie root = trie;
            for(int j = word.length - 1; j >= 0; j--) {
                char c = word[j];
                int index = c-'a';
                if(root.children[index] == null){
                    root.children[index] = new Trie();
                }
                root = root.children[index];
            }
            root.isWord = true;
        }
    }
    
    LinkedList<Character> s = new LinkedList<>();
    public boolean query(char letter) {
        s.push(letter);
        if(s.size() > maxWordLen) s.removeLast();//切掉前面的字符
        //判断后缀是否存在字典树trie中 转化为判断前缀
        Trie root = trie;
        for(int i = 0; i < s.size(); i++) {
            int index = s.get(i)-'a';
            if(root.children[index] == null) return false;
            else{
                if(root.children[index].isWord) return true;
                root = root.children[index];
                if(root == null) return false;
            }
        }
        return false;
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 */

2023-03-24