745. Prefix and Suffix Search LeetCode Solution

Last updated: February 19, 2025

In this guide, you will get 745. Prefix and Suffix Search LeetCode Solution with the best time and space complexity. The solution to Prefix and Suffix Search problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Prefix and Suffix Search solution in C++
Prefix and Suffix Search solution in Java
Prefix and Suffix Search solution in Python
Additional Resources

745. Prefix and Suffix Search LeetCode Solution image

Problem Statement of Prefix and Suffix Search

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

Constraints:

1 <= words.length <= 104
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i], pref and suff consist of lowercase English letters only.
At most 104 calls will be made to the function f.

Complexity Analysis

Time Complexity: O(|\texttt{words}||\texttt{word[i]}|^3) + O(q|\texttt{word[i]}|)
Space Complexity: O(|\texttt{words}||\texttt{word[i]}|^3)

745. Prefix and Suffix Search LeetCode Solution in C++

class WordFilter {
 public:
  WordFilter(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i) {
      const string& word = words[i];
      vector<string> prefixes;
      vector<string> suffixes;
      for (int j = 0; j <= word.length(); ++j) {
        const string prefix = word.substr(0, j);
        const string suffix = word.substr(j);
        prefixes.push_back(prefix);
        suffixes.push_back(suffix);
      }
      for (const string& prefix : prefixes)
        for (const string& suffix : suffixes)
          keyToIndex[prefix + '_' + suffix] = i;
    }
  }

  int f(string prefix, string suffix) {
    const string key = prefix + '_' + suffix;
    if (const auto it = keyToIndex.find(key); it != keyToIndex.cend())
      return it->second;
    return -1;
  }

 private:
  unordered_map<string, int> keyToIndex;
};
/* code provided by PROGIEZ */

745. Prefix and Suffix Search LeetCode Solution in Java

class WordFilter {
  public WordFilter(String[] words) {
    for (int i = 0; i < words.length; ++i) {
      final String word = words[i];
      List<String> prefixes = new ArrayList<>();
      List<String> suffixes = new ArrayList<>();
      for (int j = 0; j <= word.length(); ++j) {
        final String prefix = word.substring(0, j);
        final String suffix = word.substring(j);
        prefixes.add(prefix);
        suffixes.add(suffix);
      }
      for (final String prefix : prefixes)
        for (final String suffix : suffixes)
          keyToIndex.put(prefix + '_' + suffix, i);
    }
  }

  public int f(String prefix, String suffix) {
    final String key = prefix + '_' + suffix;
    if (keyToIndex.containsKey(key))
      return keyToIndex.get(key);
    return -1;
  }

  private Map<String, Integer> keyToIndex = new HashMap<>();
}
// code provided by PROGIEZ

745. Prefix and Suffix Search LeetCode Solution in Python

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  int weight = -1;
  TrieNode() : children(27) {}
};

class Trie {
 public:
  void insert(const string& word, int weight) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
      node->weight = weight;
    }
  }

  int startsWith(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        return -1;
      node = node->children[i];
    }
    return node->weight;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
};

class WordFilter {
 public:
  WordFilter(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i)
      for (int j = 0; j <= words[i].length(); ++j)
        trie.insert(words[i].substr(j) + '{' + words[i], i);
  }

  int f(string prefix, string suffix) {
    return trie.startsWith(suffix + '{' + prefix);
  }

 private:
  Trie trie;
};
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents