Last updated on October 25th, 2024 at 10:26 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

Prefix and Suffix Search LeetCode Solution

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 the words in the dictionary.
• f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. 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