Question

1032. Stream of Characters

中文文档

Description

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

• StreamChecker(String[] words) Initializes the object with the strings array words.
• boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

 

Example 1:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

Explanation
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
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

 

Constraints:

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 200
• words[i] consists of lowercase English letters.
• letter is a lowercase English letter.
• At most 4 * 104 calls will be made to query.

Solutions

Solution 1

class Trie:
  def __init__(self):
    self.children = [None] * 26
    self.is_end = False

  def insert(self, w: str):
    node = self
    for c in w[::-1]:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
    node.is_end = True

  def search(self, w: List[str]) -> bool:
    node = self
    for c in w[::-1]:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        return False
      node = node.children[idx]
      if node.is_end:
        return True
    return False


class StreamChecker:
  def __init__(self, words: List[str]):
    self.trie = Trie()
    self.cs = []
    self.limit = 201
    for w in words:
      self.trie.insert(w)

  def query(self, letter: str) -> bool:
    self.cs.append(letter)
    return self.trie.search(self.cs[-self.limit :])


# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)

class Trie {
  Trie[] children = new Trie[26];
  boolean isEnd = false;

  public void insert(String w) {
    Trie node = this;
    for (int i = w.length() - 1; i >= 0; --i) {
      int idx = w.charAt(i) - 'a';
      if (node.children[idx] == null) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
    }
    node.isEnd = true;
  }

  public boolean query(StringBuilder s) {
    Trie node = this;
    for (int i = s.length() - 1; i >= 0; --i) {
      int idx = s.charAt(i) - 'a';
      if (node.children[idx] == null) {
        return false;
      }
      node = node.children[idx];
      if (node.isEnd) {
        return true;
      }
    }
    return false;
  }
}

class StreamChecker {
  private StringBuilder sb = new StringBuilder();
  private Trie trie = new Trie();

  public StreamChecker(String[] words) {
    for (String w : words) {
      trie.insert(w);
    }
  }

  public boolean query(char letter) {
    sb.append(letter);
    return trie.query(sb);
  }
}

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

class Trie {
public:
  vector<Trie*> children;
  bool isEnd;

  Trie()
    : children(26)
    , isEnd(false) {}

  void insert(string& w) {
    Trie* node = this;
    reverse(w.begin(), w.end());
    for (char& c : w) {
      int idx = c - 'a';
      if (!node->children[idx]) {
        node->children[idx] = new Trie();
      }
      node = node->children[idx];
    }
    node->isEnd = true;
  }

  bool search(string& w) {
    Trie* node = this;
    for (int i = w.size() - 1; ~i; --i) {
      int idx = w[i] - 'a';
      if (!node->children[idx]) {
        return false;
      }
      node = node->children[idx];
      if (node->isEnd) {
        return true;
      }
    }
    return false;
  }
};

class StreamChecker {
public:
  Trie* trie = new Trie();
  string s;

  StreamChecker(vector<string>& words) {
    for (auto&& w : words) {
      trie->insert(w);
    }
  }

  bool query(char letter) {
    s += letter;
    return trie->search(s);
  }
};

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

type Trie struct {
  children [26]*Trie
  isEnd  bool
}

func newTrie() Trie {
  return Trie{}
}

func (this *Trie) Insert(word string) {
  node := this
  for i := len(word) - 1; i >= 0; i-- {
    idx := word[i] - 'a'
    if node.children[idx] == nil {
      node.children[idx] = &Trie{}
    }
    node = node.children[idx]
  }
  node.isEnd = true
}

func (this *Trie) Search(word []byte) bool {
  node := this
  for i := len(word) - 1; i >= 0; i-- {
    idx := word[i] - 'a'
    if node.children[idx] == nil {
      return false
    }
    node = node.children[idx]
    if node.isEnd {
      return true
    }
  }
  return false
}

type StreamChecker struct {
  trie Trie
  s  []byte
}

func Constructor(words []string) StreamChecker {
  trie := newTrie()
  for _, w := range words {
    trie.Insert(w)
  }
  return StreamChecker{trie, []byte{}}
}

func (this *StreamChecker) Query(letter byte) bool {
  this.s = append(this.s, letter)
  return this.trie.Search(this.s)
}

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