Search a String in the Dictionary with the Given Prefix and Suffix

In this tutorial, we will write the Python program to search a string in the dictionary with the given prefix and a suffix. We are given an array, consisting of N string and Q queries in the form of two strings prefix and suffix. Our task is to get any string in the given array with the given prefix and suffix.

Let's understand the following example -

Input:

arr = ["apple", "app", "biscuit", "mouse", "orange", "bat", "microphone", "mine"}]

Queries = [{a, e}, {a, p}]

Output:

apple

app

Explanation:

Query 1:

String "apple" is the only word in the given dictionary with the given prefix "a" and suffix "e".

Query 2:

String "app" is the only word in the given dictionary with the given prefix "a" and suffix "p".

Let's solve this problem using the naïve approach.

Solution - Naïve Approach

# N is the number of strings in the array
N = 8

# Declare an array of size N
arr = ["apple", "app", "biscuit", "mouse", "orange", "bat", "mine", "mine"]

Q = [["a", "e"], ["mi", "ne"]]

for i in range(len(Q)):
    prefix = Q[i][0]
    suffix = Q[i][1]

    found = False

    for j in range(N):
        if arr[j][:len(prefix)] == prefix and arr[j][-len(suffix):] == suffix:
            print(arr[j])
            found = True
            break

    if not found:
        print("-1")

Output:

apple
mine

Explanation -

The naive approach here involves comparing the prefix and suffix of each string with the corresponding query. If the prefix and suffix match, we print the string and set the found flag to True. Otherwise, if no match is found, we print "-1" at the end of the query.

Time Complexity - The time complexity of the above program will be the O (Q*N*M), where M is the maximum length of the string.

We can solve it using the more efficient way.

Solution -

In this section, we will solve this problem using the Trie Data Structure. It can support both prefix and suffix search in the following way -

To support prefix and suffix search simultaneously, the word "apple" can be inserted into a Trie data structure. Additionally, variations of the word can also be inserted to facilitate efficient prefix and suffix search. For instance, the words "e{apple," "le{apple," "ple{apple," "pple{apple," and "apple{apple" can be inserted into the Trie.

Each word in the Trie will be of the form "suffix {word," where "suffix" represents all the possible suffixes obtained from the given word "apple."

The special character { is inserted to separate the suffix and word to separate them. Any other special character can be used in place of { but { is preferred because its ASCII value is 123.

Following are the steps to solve the problem -

First, traverse the string in the given array and perform the following steps -

Initialize a string temp as '{' + arr[i].
Iterate over all the characters in the string arr[i] from the end. For each character, append it to the front of the string temp, and then insert this string into the Trie data structure.
After creating the Trie, iterate over all the queries, and for each query, do the following:
1. Store the prefix and suffix strings for the current query.
2. Initialize a string t as suffix + '{' + prefix and search for it in the Trie.
3. If the string t is not found in the Trie, print "-1".
4. Otherwise, print the matching string found in the Trie.

Let's understand the following example -

Example -

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

def insert_suffixes_into_trie(trie, word):
    for i in range(len(word) - 1, -1, -1):
        temp = '{' + word[i:]
        trie.insert(temp)

def find_matching_word(trie, prefix, suffix):
    t = suffix + '{' + prefix
    return trie.search(t)

# Example usage:
if __name__ == "__main__":
    words = ["apple"]
    queries = [["e", "le"], ["pl", "pple"], ["x", "y"]]

    trie = Trie()
    for word in words:
        insert_suffixes_into_trie(trie, word)

    for prefix, suffix in queries:
        if find_matching_word(trie, prefix, suffix):
            print("Matching word found for prefix '{}' and suffix '{}'.".format(prefix, suffix))
        else:
            print("-1")

Output:

apple
mine

Explanation -

In this code, we first define the TrieNode and Trie classes to create and work with the Trie data structure. The insert method is used to insert a word into the Trie, and the search method is used to search for a word in the Trie.

The insert_suffixes_into_trie() function takes a Trie and a word as input and inserts all the possible suffixes of the word into the Trie.

The find_matching_word() function takes a Trie, prefix, and suffix as input and constructs a string t in the format "suffix{prefix" and searches for it in the Trie.

Time Complexity - The time complexity is O (N*M2 + Q*M), where M is the maximum length of among all the strings.

Conclusion

In conclusion, the topic discussed the concept of using a Trie data structure to efficiently support prefix and suffix search simultaneously for a given set of words. A Trie is a tree-like data structure that is particularly useful for handling and searching large collections of strings.

Next TopicSorting using Trivial Hash Function

← prev next →