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.

 

Example:

StreamChecker 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

 

Note:

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 2000
• Words will only consist of lowercase English letters.
• Queries will only consist of lowercase English letters.
• The number of queries is at most 40000.

TLE Version (First Draft)

This is the version I submitted during the contest, TLE. (obviously, for a hard question)

My idea was building a tree, well, I just hate writing another class…. so I tried in a hard way during the contest.

class StreamChecker {
    public $max = 0;
    public $hist = "";
    public $d;

    /**
     * @param String[] $words
     */
    function __construct($words) {
        error_reporting(0);
        ini_set('display_errors', 0);
        $this-> d = $words;
        foreach($words as $w){
           $this ->max = max(strlen($w), $this ->max); 
        }
        
    }
  
    /**
     * @param String $letter
     * @return Boolean
     */
    function query($letter) {

        $this ->hist .= $letter;
        foreach($this->d as $f){
            if ($this -> endsWith($this -> hist,$f)) {
                
                return true;
            }
        } 
        if(strlen($this->hist) > $max){
            $this->hist = substr($this->hist, -($this->max));
        }
        
        return false;
    }
    
    function endsWith($haystack, $needle)
    {
        $length = strlen($needle);
        if ($length == 0) {
            return true;
        }
        return (substr($haystack, -$length) === $needle);
    }
}

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

Another Try

for the query part, if the char is not the last char of any word in the dictionary, return false. The method actually passed all the tests, 2000+ms.

It’s actually a single level trie tree..   in the form of an array.

 

class StreamChecker {
    public $max = 0;
    public $hist = "";
    public $first = [];
    public $d;

    /**
     * @param String[] $words
     */
    function __construct($words) {
        error_reporting(0);
        ini_set('display_errors', 0);
        $this-> d = $words;
        foreach($words as $w){
            $this ->max = max(strlen($w), $this ->max); 
            $this -> first[] = $w[strlen($w)-1];
        }
        
    }
  
    /**
     * @param String $letter
     * @return Boolean
     */
    function query($letter) {
        $this ->hist .= $letter;
        if(!in_array($letter,$this->first)){
            return false;
        }
        foreach($this->d as $f){
            if ($this -> endsWith($this -> hist,$f)) {
                
                return true;
            }
        } 
        if(strlen($this->hist) > $max){
            $this->hist = substr($this->hist, -($this->max));
        }
        
        return false;
    }
    
    function endsWith($haystack, $needle)
    {
        $length = strlen($needle);
        if ($length == 0) {
            return true;
        }
        return (substr($haystack, -$length) === $needle);
    }
}

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