Prefix Suffix Search in Java
Create a unique dictionary that searches for words in it using prefixes and suffixes. To do this, we must implement the WordFilter class in a way that initializes the object with the dictionary words: WordFilter(string[] words).
The dictionary index containing the prefix pref and the suffix suff is returned by the function find(string pref, string suff). Return the largest valid index if there are many. Return -1 if the dictionary does not contain the term in question.
The user must put the new "PRE_SUF_SEARCH" data structure into use. With the help of this data structure, you can search for a word using its prefix and suffix in "PRE_SUF_SEARCH."
Example 1:
Input:
["bat", ["b", "t"]]
["rat",["rr", "t"]]
Output:
1
-1
Explanation:
Prefix "b" and suffix "t" are present in "bat" for query 1, which returns the largest index.
There is not a single term with the prefix "rr" in the "PRE_SUF_SEARCH" for query 2. Hence, it returns the output as 0.
There are different approaches to solving this problem.
Approach: If find() is more frequently than WordFilter(),
WordFilter Class (Constructor):
The constructor of the WordFilter class accepts an array of words (String[] words) as input. It initializes a HashMap named map, which holds key-value pairs. The values are the indices of the words in the input array, and the keys are made up of the prefixes and suffixes of each word, separated by the asterisk (#). It goes through every word in the input array one by one.
It creates all conceivable prefix and suffix combinations (ranging from 0 to a maximum of 10 characters for each prefix and suffix) for each word. By using # as a separator to concatenate prefixes and suffixes, it creates keys that are then stored in the map and linked to the word index in the input array.
f Method: Using a prefix and a suffix as input, this method determines whether the prefix-suffix combination is present in the map as a key. It returns the word's matching index if it exists; if not, it returns -1 to show that the term could not be located.
Implementation:
FileName: WordFilterPrefixSuffix
import java.io.*;
import java.util.*;
public class WordFilterPrefixSuffix
{
HashMap<String, Integer> map = new HashMap<>();
public WordFilterPrefixSuffix(String[] words)
{
for(int word = 0; word < words.length; word++)
{
// It produces each possible combination of prefixes and suffixes
// with a limit of ten characters for each combination.
for(int i = 0; i <= 10 && i <= words[word].length(); i++)
{
for(int j = 0; j <= 10 && j <= words[word].length(); j++)
{
// Using # as a separator concatenates the prefixes and suffixes to create keys,
// which are then stored in the map HashMap and linked to the word index in the input array.
map.put(words[word].substring(0, i) + "#" + words[word].substring(words[word].length()-j), word);
}
}
}
}
public int f(String prefix, String suffix)
{
// It returns the word's matching index if the key is present;
//If not, it returns -1, indicating that the word could not be located
return (map.containsKey(prefix + "#" + suffix))? map.get(prefix + "#" + suffix) : -1;
}
public static void main(String[] args)
{
String[] words = {"banana", "grape"};
WordFilterPrefixSuffix wordFilter = new WordFilterPrefixSuffix(words);
System.out.println(wordFilter.f("ban", "na"));
System.out.println(wordFilter.f("gra", "pe"));
}
}
Output:
0
1
Complexity Analysis:
The time complexity for WordFilter is O(NL^2), and for find(), the time complexity is O(1). The space complexity is O(NL^2), where N is the size of an array, and L is the maximum length of strings taken.
Approach: Concerning the space complexity
With the assistance of separate HashMaps, this approach optimizes prefix and suffix searching by keeping lists of word indices connected to each prefix and suffix. It obtains lists of word indices connected to prefixes and suffixes when searching for them. The term that satisfies the specified prefix and suffix criteria is then indicated by the maximum index present in both lists, which is found by comparing the two lists.
Implementation:
FileName: WordFilterSpaceComplexity.java
import java.io.*;
import java.util.*;
public class WordFilterSpaceComplexity
{
// creating the hashmaps for prefix and suffix
HashMap<String, List<Integer>> Prefix = new HashMap<>();
HashMap<String, List<Integer>> Suffix = new HashMap<>();
public WordFilterSpaceComplexity(String[] words)
{
// implementing the wordFilter PRE_SUF_SEARCH for the words present in the dictionary
for(int word = 0; word < words.length; word++)
{
// The word's index is appended to the list in mapPrefix corresponding to each prefix.
for(int i = 0; i <= 10 && i <= words[word].length(); i++)
{
String str = words[word].substring(0, i);
if(!Prefix.containsKey(str)) Prefix.put(str, new ArrayList<>());
Prefix.get(str).add(word);
}
// The word's index is appended to the list in mapSuffix corresponding to each suffix.
for(int i = 0; i <= 10 && i <= words[word].length(); i++)
{
String str = words[word].substring(words[word].length() - i);
if(!Suffix.containsKey(str)) Suffix.put(str, new ArrayList<>());
Suffix.get(str).add(word);
}
}
}
public int f(String prefix, String suffix)
{
// obtains the lists of indices connected to the given suffix and prefix.
if(!Prefix.containsKey(prefix) || !Suffix.containsKey(suffix)) return -1;
List<Integer> pre = Prefix.get(prefix);
List<Integer> suf = Suffix.get(suffix);
int i = pre.size()-1, j = suf.size()-1;
while(i >= 0 && j >= 0)
{
// In order to determine the greatest index that is present in both lists at the same time,
// iterate backward, starting at the end of each list.
if(pre.get(i) < suf.get(j))
j--;
else if(pre.get(i) > suf.get(j))
i--;
// It returns -1 if no match is found, which means that
//The word with the supplied prefix and suffix was not located.
else
return pre.get(i);
}
return -1;
}
public static void main(String[] args)
{
String[] words = {"banana", "grape"};
WordFilterSpaceComplexity wordFilter = new WordFilterSpaceComplexity(words);
System.out.println(wordFilter.f("ban", "na"));
System.out.println(wordFilter.f("gra", "pe"));
}
}
Output:
0
1
Complexity Analysis:
The WordFilter Class Time complexity is O(NL), and the Time Complexity for find() is O(N). The Space Complexity is O(NL), where N is the size of an array, and L is the maximum length of strings taken.
Approach: If WordFilter() is more frequently than find()
The f method iterates through the word array in reverse in this code, using a simple approach. It determines if each word begins with the specified prefix and finishes with the specified suffix for each word. It returns its index if a word of that kind is found. However, because of its linear time complexity (O(n)) for each query, this method could not be as efficient as alternative solutions, particularly when working with larger datasets or extensive searches.
Implementation:
FileName: WordFilterFind.java
import java.io.*;
import java.util.*;
public class WordFilterFind
{
String[] in;
public WordFilterFind(String[] words)
{
in = words;
}
public int f(String prefix, String suffix)
{
// Checks whether the term begins with the
// specified prefix and completes with the specified suffix.
for(int i = in.length-1; i >= 0; i--)
{
// It returns the word’s index if one of the two conditions
// is true for each given word.
// else returns -1
if(in[i].startsWith(prefix) && in[i].endsWith(suffix))
return i;
}
return -1;
}
public static void main(String[] args)
{
String[] words = {"banana", "grape"};
WordFilterFind wordFilter = new WordFilterFind(words);
System.out.println(wordFilter.f("ban", "na"));
System.out.println(wordFilter.f("gra", "pe")); }
}
Output:
0
1
Complexity Analysis:
The time complexity for the WordFilter class is O(1), and the time complexity for find() is O(NL). The Space Complexity is O(1).