LeetCode 1032. Stream of Characters

题意：如果你稍微了解关于大数据/视频/音频流(Stream)处理的背景的话，你会觉得这道题非常棒。简单介绍下流处理，举个简单的例子，你在Youtobe上观看电影的时候不需要事先下载整个电影文件，而是进行缓存加载，来一点播放一点。前端视频代码需要对最近收到的视频文件进行检测，就要用到这个StreamChecker。

用字典树即可解决。首先在init的时候，把words中所有word逆置后存入字典树中；在query的时候，也有逆序的方式记录所有历史query过的值，同时判断其前缀是否存在于字典树中即可。

    function Node() {
      this.children = {}
    }
    class StreamChecker {
      constructor(words) {
        this.history = ''
        this.root = new Node;
        for (let word of words) {
          this.insert(word.split('').reverse().join(''))
        }
      }
      insert(word) {
        var node = this.root;
        for (let c of word) {
          var next = node.children[c]
          if (!next) {
            node.children[c] = next = new Node
          }
          node = next;
        }
        node.word = word;
      }
      search(word) {

        var current = this.root;
        for (var i = this.history.length - 1; i >= 0; i--) {
          var ch = this.history[i]
          if (current.children[ch] == null) {
            return false;
          }
          current = current.children[ch];
          if (current.word) {
            return true;
          }
        }
        return false

      }
      query(q) {
        this.history += q
        var val = this.search()
        console.log(val)
        return val
      }

    }

    var streamChecker = new StreamChecker(["cd", "f", "kl"]); // init the dictionary.
    streamChecker.query('a');          // return false
    streamChecker.query('b');          // return false
    streamChecker.query('c');          // return false
    streamChecker.query('d');          // return true, because 'cd' is in the wordlist
    streamChecker.query('e');          // return false
    streamChecker.query('f');          // return true, because 'f' is in the wordlist
    streamChecker.query('g');          // return false
    streamChecker.query('h');          // return false
    streamChecker.query('i');          // return false
    streamChecker.query('j');          // return false
    streamChecker.query('k');          // return false
    streamChecker.query('l');          // return true, because 'kl' is in the wordlist

本文内容仅供个人学习/研究/参考使用，不构成任何决策建议或专业指导。分享/转载时请标明原文来源，同时请勿将内容用于商业售卖、虚假宣传等非学习用途哦～感谢您的理解与支持！

链接: https://fly63.com/article/detial/8562