Last updated on August 3rd, 2024 at 10:12 pm
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
Topics
Binary Search
Level of Question
Hard
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”.
1. 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; } };
2. 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; } }
3. 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; }
4. 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