[Google] Check All Numbers Given the Decimal Scale

Question

“00110, a=2, k=2” => true （包括了00，01，10，11）

Solution

First find all substrings with length == k, then generate all numbers in a scale. This is not a difficult question.

We may want to score the substrings in a HashMap/HashSet. The hashing procedure is preferrably using Rolling hash.

Rolling Hash

A rolling hash is a hash function where the input is hashed in a window that moves through the input.

A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters.

Rolling Hash is commonly used in Rabin-Karp Algorithm to speed up strStr() string pattern matching.

People in the origin post - they discuss about “slide window check” algorithm. I do not understand what’s the benefit of this. If you read this and would like to help me, please leave a comment. Thanks!

A similar question

This is simply the reverse of the question above:

This question is solved using De Bruijn sequence.