Algorithmic Deep-dive: Dynamic String Matching

Setup

Consider a minimalistic and austere typing game wherein a player is required to type a bunch of words appearing on the screen before the timer expires.

Something like this:

The entire implementation of the game is here

Okay! Lets get to it then.

Problem

Lets consider the problem of actually matching the player string to the list of words. The typical implementation of it would work something like this:

• Record the player input, we will refer to its present state as player_string
• When the player hits enter, match the current player string with the list of words like

if player_string in word_list:
    # do something

The time complexity of this is O(len(player_string)*len(word_list)), which is fine if we are only processing such matching when the player hits enter. But say we don't want that, what we want is whenever the player presses any key, the player_string is matched with words in the word_list. Now the earlier time complexity seems a bit extraneous and we will try to come with a more elegant and efficient approach to solve this.

Requirements

Before going into the nitty-gritty of the different approaches used, let us take a pause and list down our exact requirements.

1. The string matching needs to be done with each keystroke, not just when player hits enter.
2. We should support the following user actions:
   • The player can insert an alphanumeric character.
   • The player can delete the character left of the cursor position, if any, by pressing backspace.
   • The player can move the cursor position using the left-right direction keys.

Trie Approach

If you are not familiar with the Trie data structure, refer here1,
here2. Very briefly, Trie or prefix tree is a data structure that stores a list of strings in a tree structure and helps maintain the time complexity of many operations like insertion, deletion and search to order of O(len(word)). Note Trie can be used in various contexts other than just strings, refer here3 to understand how tries can be used to solve bit manipulation questions.

Now that we have got the introductions out of the way, lets see how Tries are relevant to our problem. Tries are pertinent to us in two ways:

1. Store the list of words:

Something like
The time required to store all the words in the list will be of order O(n*m), where n = len(words) and m = max(len(word))

1. Check if the player_string matches with any word:

Now, if you're following along, this part is rather trivial. We start at the root of the tree and for every character entered we traverse the tree accordingly and if we ever arrive at a node with last == True, VOILA! there is a match and we can strike that word out from the list, easy peasy.

But what happens if the player presses backspace, our data structure still doesn't have the capability to process this user action. A typical Trie implementation doesn't support going back along a path but this can be easily added by either appending an extra attribute parent to each trie node that way we can move back one node whenever the user presses backspace or the way I did it, by augmenting a list to keep track of all the nodes we have visited while traversing some input and then popping nodes from this list with each backspace. This does increase the space complexity to O(len(word)) but keeps the time complexity to O(1) for insertion and backspace user actions.

The implementation for this Trie based approach can be found here

Rolling hash + Deque Approach

The problem with Trie based approach is that, at least to the best of my knowledge, there's no way to incorporate the cursor moving actions. Come to think of it this does make sense, Trie or prefix tree, is a data structure which is designed to process, no surprises here, prefixes and as soon a player starts moving his/her cursor and start typing from arbitrary positions in the string that prerequisite is broken. So what do we do?

Rolling hash comes to the rescue. Rolling hash is a hashing technique which processes one character at a time for computing the hash value and depending how one implements it, can efficiently recompute hash values if some character(s) are to inserted/deleted. Rolling hash is used in the Rabin Karp algorithm for pattern matching here1 and also palindrome based queries here2.

Rolling hash intuitively fits the bill as it allows us to efficiently compute hash values for insertion and deletion operations. But what about the cursor moving actions? Well, for that we have to employ deques to dynamically maintain characters to the right and left of the cursor position. This approach works this way:

1. Store the list of words:

We compute the hash value for all the words in the list and store them in a dictionary.

1. Check if the player_string matches with any word:

We dynamically compute the hash value of the player_string with each user action and check if the hash value is present in the dictionary of stored hashes, if yes then we ensure that the strings actually match by brute-force string-matching of the player_string with the potential match.

This approach maintains a time complexity of O(log(mod)) per user action, where mod is the modulo used in calculating the hash values of the strings. Note that this approach does depend on the uniqueness of the hashing algorithm and key space used. For this instance I used a modulo closer to ~10^10.

The implementation of this Rolling hash + Deque approach can be found here

So that's it, the rolling hash + deque approach maintains a minimal time complexity for our problem while supporting all the intended user actions.

I've tried to explain the approaches and their essential points succinctly and so they may not be a 100% comprehensive but do look at the code, I believe that will clear a lot of confusion. Plus do comment if you believe anything is wrong or you think there is a more elegant or efficient way of solving this, I would love to learn about it.