Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Prefix and Suffix Search

Prefix and Suffix Search

Solve a hard-level problem of finding words that start with a given prefix and end with a given suffix using tries.

We'll cover the following...

Problem statement

Given a list of words and two strings pre and suff, return the index of the word that has pre as its prefix and suff as its suffix. If there are multiple valid answers, then return the bigger index. Return -1 if no valid word exists in the list.

Please note that the words list is zero-indexed.

Example 1

Sample input

words: ["app", "apple", "apply", "applicable"]
pref: "a"
suff: "y"

Sample output

2

Explanation

The word at index 2, "apply", has prefix as "a" and suffix as "y".

Example 2

Sample input

words: ["app", "apple", "apply", "applicable"]
pre: "a"
suff: "e"

Sample output

3

Explanation

The word at index 1, "apple" has "a" as a prefix and "e" as a suffix. The word at index 3, "applicable" has "a" as a prefix and "e" as a suffix. Therefore, the bigger index, 3, is returned as an answer.

Try it yourself

Please try to solve the problem yourself before reading the solution. 

#include <iostream>

#include <vector>

using namespace std;



int findWordsWithPrefAndSuff(vector<string>& words, string pref, string suff) {

  // your code goes here

  return -1;

}
Solve prefix and suffix search in C++

Intuition

This problem can be solved by dividing the solution into three smaller parts, tackling prefix and suffix searching separately, and then finding the intersection of the two valid arrays.

Algorithm

The summary of the algorithm is given below.

Step 1: Prefix Search

Given a list of words and a prefix string, we can easily identify the word with the given prefix using tries.

Insert all the words into a trie. Iterate using the prefix string and return a list of all valid words starting with this prefix; these would be all the child words in the trie for the last node of the prefix string.

Let's use an example. As shown in the illustration below, there are three valid words: apply, apple, ape.
Let's search for all the words with the prefix ap in the trie. If we traverse for the string ap, all the child nodes after the node p in the trie would have ap as their prefix. Therefore, all the words in the subtree below ap would be the list of valid words with ap as a prefix. So, we need to return all the child nodes of the last character of the prefix string (i.e., p node in the trie) that are valid words.

After performing this step, we've extracted a list of words that can be possible valid answers. The actual valid words will be the ones that satisfy the suffix condition as well. Now, let's dive in to the second part of the problem: suffix searching.

Step 2: Suffix Search

In essence, suffix is the opposite of prefix. While searching for a prefix in a string, we start from the first character of the string. Similarly, while searching for a suffix in the string, we start from the last letter of the string.

But if we start matching the characters in a trie bottom up (i.e., from leaf nodes up to the root nodes), the process will be clumsy and inefficient as there can be multiple leaf nodes to begin from.

An easier way is to construct the trie from reversed words and perform prefix searching for the given suffix string.

Let's create a trie of the words epa, elppa, ylppa. Notice the words are reversed.

Now we can directly search for the prefix e in the suffix tree and return the children of the node e, which are valid words. In this case, the words will be ape and apple. The search here is similar to the one done in prefix searching above. ...