Algorithmic Deep-dive: Dynamic String Matching
Tags: algorithms, tutorial, python, datastructures
Published: 2020-11-08 12:19:31

##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:
![Pygame Typing Challenge](https://dev-to-uploads.s3.amazonaws.com/i/x7ibq94kbllbkkjpdt4l.PNG)

The entire implementation of the game is [here](https://github.com/anirudnits/Pygame-Typing-Challenge)

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

```python
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](https://www.youtube.com/watch?v=AXjmTQ8LEoI),
[here2](https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/tutorial/). 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](https://www.hackerearth.com/practice/notes/lalitkundu95/tutorial-on-trie-and-example-problems/) 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 ![Trie data structure to store words](https://dev-to-uploads.s3.amazonaws.com/i/fb1azzu32cpkvatfyb8e.jpg)
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))

2. 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](https://github.com/anirudnits/Pygame-Typing-Challenge/blob/4b79ea29dfac1e086c64848bb94daea03657f0b9/data_structures.py#L25)

##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](https://en.wikipedia.org/wiki/Rolling_hash) and also palindrome based queries [here2](https://www.quora.com/q/threadsiiithyderabad/String-Hashing-for-competitive-programming?share=1).

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.

2. 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](https://github.com/anirudnits/Pygame-Typing-Challenge/blob/4b79ea29dfac1e086c64848bb94daea03657f0b9/data_structures.py#L64)
 
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.