Last updated on January 19th, 2025 at 02:31 am

Here, we see a Prefix and Suffix Search LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search

Level of Question

Hard

Prefix and Suffix Search LeetCode Solution

1. 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”.

2. Coding Pattern Used in Solution

The coding pattern used in all the implementations is Trie (Prefix Tree) combined with Hash Map. The problem involves efficiently searching for words based on a prefix and suffix, which is well-suited for a Trie data structure.

3. Code Implementation in Different Languages

3.1 Prefix and Suffix Search 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;
    }
};

3.2 Prefix and Suffix Search 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.3 Prefix and Suffix Search 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;
}

3.4 Prefix and Suffix Search 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

4. Space Complexity

	Space Complexity
C++	O(n * l²)
Java	O(n * l²)
JavaScript	O(n * l²)
Python	O(n * l²)

Here,

n: Number of words in the input list.
l: Average length of a word.