leetcode1032

Implement the StreamChecker class as follows:

StreamChecker(words): Constructor, init the data structure with the given words.
query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

把所有输入转化成一棵树,每次查询就是遍历这棵树(倒序)
预处理生成树注意会有一个遍历结束标记
每次输入,从根节点依次往下遍历即可.

class StreamChecker {
  private Node root = new Node();
  private char[] a = new char[40001];
  private int len = 0;
  
  public StreamChecker(String[] words) {
    int len = words.length;
    for(int i=0;i<len;i++) {
      addNodes(words[i], root);
    }
  }

  private void addNodes(String str,Node root){
    int len = str.length();
    Node node = root;
    for (int i=len-1;i>=0;i--){
      node = node.getNodeWithCreate(str.charAt(i));
    }
    node.setYz();
  }

  public boolean query(char letter) {
    int i = len;
    a[len] = letter;
    len++;
    Node node = root;
    while(i>=0){
      if (node.isYz()){
        return true;
      }
      node =  node.getNode( a[i]);
      if (node==null){
        return false;
      }
      i--;
    }
    return node.isYz();
  }

  private class Node{
    private Node[] sons = new Node[26];
    private boolean isYz = false;
    private Node getNodeWithCreate(char c){
      Node node =  sons[c-'a'] ;
      if (node==null){
      
        node = new Node();
        sons[c-'a'] = node;
      }
      return node;
    }

    private  Node  getNode(char c){
      return  sons[c-'a'];
    }

    private void setYz(){
      isYz = true;
    }
    private boolean isYz(){
      return isYz;
    }
  }

}

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

近期文章

近期评论

标签

热门

文章归档

分类目录

功能