Here, We see Prefix and Suffix Search LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Prefix and Suffix Search LeetCode Solution
Table of Contents
Problem Statement
Design a special dictionary that searches the words in it by a prefix and a suffix.
Implement the WordFilter
class:
WordFilter(string[] words)
Initializes the object with thewords
in the dictionary.f(string pref, string suff)
Returns the index of the word in the dictionary, which has the prefixpref
and the suffixsuff
. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return-1
.
Example 1:
Input [“WordFilter”, “f”] [[[“apple”]], [“a”, “e”]]
Output [null, 0]
Explanation WordFilter wordFilter = new WordFilter([“apple”]); wordFilter.f(“a”, “e”); // return 0, because the word at index 0 has prefix = “a” and suffix = “e”.
Prefix and Suffix Search LeetCode Solution C++
class WordFilter {
public:
unordered_map<string, int> mp;
WordFilter(vector<string>& words)
{
int n = words.size();
for(int i=0; i<n; i++)
{
string word = words[i];
int wordsize = word.size();
for(int j=1; j<=wordsize; j++)
{
string pre = word.substr(0,j);
for(int k=0; k<wordsize; k++)
{
string suff = word.substr(k, wordsize);
mp[pre + "|" + suff] = i+1;
}
}
}
}
int f(string prefix, string suffix)
{
string s = prefix + "|" + suffix;
return mp[s]-1;
}
};
Code language: PHP (php)
Prefix and Suffix Search LeetCode Solution Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public List<Integer> vals = new ArrayList<>();
}
class WordFilter {
private TrieNode pTrie = new TrieNode();
private TrieNode sTrie = new TrieNode();
public WordFilter(String[] words) {
Set<String> wordSet = new HashSet<>();
for (int index = words.length - 1; index > -1; index--) {
if (wordSet.contains(words[index]))
continue;
wordSet.add(words[index]);
char[] word = words[index].toCharArray();
int wlen = word.length;
insert(word, index, pTrie, 0, wlen, 1);
insert(word, index, sTrie, wlen-1, -1, -1);
}
}
private void insert(char[] word, int index, TrieNode trie, int start, int end, int step) {
for (int i = start; i != end; i += step) {
int c = word[i] - 'a';
if (trie.children[c] == null)
trie.children[c] = new TrieNode();
trie = trie.children[c];
trie.vals.add(index);
}
}
private List<Integer> retrieve(char[] word, TrieNode trie, int start, int end, int step) {
for (int i = start; i != end; i += step) {
trie = trie.children[word[i]-'a'];
if (trie == null) return new ArrayList<>();
}
return trie.vals;
}
public int f(String pref, String suff) {
List<Integer> pVals = retrieve(pref.toCharArray(), pTrie, 0, pref.length(), 1);
List<Integer> sVals = retrieve(suff.toCharArray(), sTrie, suff.length()-1, -1, -1);
int svix = 0, pvix = 0;
while (svix < sVals.size() && pvix < pVals.size()) {
int sVal = sVals.get(svix), pVal = pVals.get(pvix);
if (sVal == pVal) return sVal;
if (sVal > pVal) svix++;
else pvix++;
}
return -1;
}
}
Code language: PHP (php)
Prefix and Suffix Search Solution JavaScript
var WordFilter = function (words) {
this.map = new Map();
for (let i = 0; i < words.length; i++) {
let prefix = '';
for (let j = 0; j <= words[i].length; j++) {
let suffix = '';
for (let k = 0; k <= words[i].length; k++) {
suffix = words[i].slice(k);
this.map.set(prefix + '#' + suffix, i);
}
prefix += words[i][j];
}
}
}
WordFilter.prototype.f = function (prefix, suffix) {
let target = prefix + '#' + suffix;
return this.map.has(target) ? this.map.get(target) : -1;
}
Code language: JavaScript (javascript)
Prefix and Suffix Search Solution Python
class WordFilter:
def __init__(self, words):
self.pTrie = [None] * 27
self.sTrie = [None] * 27
self.wordSet = set()
for index in range(len(words)-1, -1, -1):
word = words[index]
if word not in self.wordSet:
self.wordSet.add(word)
self.insert(word, index, self.pTrie)
self.insert(word[::-1], index, self.sTrie)
def insert(self, word, index, trie):
for c in word:
cval = ord(c) - 97
if not trie[cval]: trie[cval] = [None] * 27
trie = trie[cval]
if not trie[26]: trie[26] = []
trie[26].append(index)
def retrieve(self, word, trie):
for c in word:
cval = ord(c) - 97
trie = trie[cval]
if not trie: return []
return trie[26]
def f(self, pref, suff):
pVals = self.retrieve(pref, self.pTrie)
sVals = self.retrieve(suff[::-1], self.sTrie)
svix, pvix = 0, 0
while svix < len(sVals) and pvix < len(pVals):
sVal, pVal = sVals[svix], pVals[pvix]
if sVal == pVal: return sVal
if sVal > pVal: svix += 1
else: pvix += 1
return -1