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

...

/

Keyword Search

Keyword Search

Solve an easy-level problem of searching a keyword in a list of strings using tries.

We'll cover the following...

Problem statement

Given two lists of words (strings), for each word in the second list, identify if the word appears as either a complete word or a prefix of any word in the first list. If it's present as a complete word, print "word". If it's present as a prefix, print "prefix". If it isn't present as either a complete word or a prefix, print "not-found".

Example 1

Sample input

list1: ["app", "apple", "apply", "ape"]
list2: ["app", "appl", "apex"]

Sample output

["word", "prefix", "not-found"]

Explanation

"app" is present as a complete word in the list1.
"appl" is a "prefix" of the word "apple", which is present in list1.
"apex" is not present in list1, neither as a prefix nor as a complete word.

Example 2

Sample input

list1: ["pay", "paid", "pad", "pat"]
list2: ["pa", "pai", "pat"]

Sample output

["prefix", "prefix", "word"]

Explanation

"pa" is a "prefix" of the words "pay", "paid", "pad" and "pat", present in list1.
"pai" is a "prefix" of the word "paid" present in list1.
"pat" is present as a complete word in list1.

Try it yourself

Try to solve the following problem yourself before reading the solution.

#include <iostream>

#include <vector>

using namespace std;



vector<string> findIsWordOrIsPrefix(vector<string>& list1, vector<string>& list2){

    // your code goes here

    vector<string> answer;

    return answer;

}
Solve keyword search in C++

Intuition

For every word of list2, this problem requires us to check two conditions. First, check if the word is present in the list1. If not, then determine if the word is present as a prefix of any string of list1.

It's visible that the problem is related to strings and prefix search. Although we can adopt the brute-force approach of comparing each word of the list2 with each word of the list1 to solve the problem, it would lead to higher time complexity. Using tries instead is an efficient data structure for prefix search-related problems. Hence, we'll use a trie data structure to solve this problem.

Algorithm

Step 1: Insertion in a trie

Insert all the words from list1 into a trie. Set the value of isEndOfWord as true for the trie node associated with the last character of the word.

Step 2: Searching in a trie

Iterate over the words of list2 to check if they're present in the trie. While searching for a word in the trie, we can encounter the following three conditions:

  • Found as a complete word: If we reach the last character of the word and isEndOfWord is set as ...

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy