Search Auto-Complete for Special Languages

Problem statement

Some languages, like Persian, are written from right to left instead of left to right. We have to design an auto-complete feature for such languages. We're provided with a list of keywords and a query string. Design a system that provides query suggestions from the keyword list to the user every time the user types a character of the query string.

Example

Sample input

Sample output

Explanation

For the query "e", words ending with "e" are ["mere", "leave"].
For the query "er", words ending with "er" are ["monster", "gangster", "meter", "hostler", "hotter"].

Try it yourself

Try to solve the problem yourself before reading the solution.

Intuition

This problem is very similar to the problem of search auto-complete. However, since we're dealing with special languages, which are written from right to left, the suggested words should be a suffix of the query string typed so far. The only difference is that in the previous problem we were searching the keywords based on the prefix, while in this case, we have to use a suffix.

This problem can also be solved using binary search, but here we'll only discuss the trie-based solution. We can observe that we're searching for all the words with a given suffix. It's well known that tries can solve suffix-related problems quickly.

Algorithm

The summary of the algorithm is given below.

Step 1: Build a trie

We create a suffix trie from the given word list input and iterate each character of the query word in reverse order, adding it to the suffix to search for. After adding the current character to the suffix, we traverse the trie pointer to the node representing the suffix.

Step 2: DFS on trie

Next, we traverse the trie from the current pointer in a preorder fashion using depth-first search. Whenever a complete word is encountered, we add it to the final result list. Completion of a word can be determined ...