Scale Engineer

Prefix and Suffix Search

Hard
#0699Time: Constructor: O(1). `f` method: O(N * L) for each call, where N is the number of words and L is the maximum length of a word. The string matching operations `startsWith` and `endsWith` can take up to O(L) time. For Q queries, the total time complexity is O(Q * N * L).Space: O(N * L), where N is the number of words and L is the maximum length of a word. This space is used to store the dictionary of words itself.1 company
Patterns
Design
Data structures
ArrayHash TableStringTrie
Companies
Rubrik

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach. The constructor does minimal work, simply storing the list of words. For each query to the f function, we iterate through the entire list of words to find one that matches the given prefix and suffix.

Algorithm

  • In the WordFilter constructor, store the input words array.
  • In the f(pref, suff) method, iterate through the words array from the last index (words.length - 1) down to 0.
  • For each word at index i:
    • Use string functions to check if word.startsWith(pref) and word.endsWith(suff).
    • If both conditions are true, it means we've found a match. Since we are iterating backwards, this is the match with the largest index. Return i immediately.
  • If the loop completes without finding any matches, return -1.

Walkthrough

The WordFilter constructor initializes the object by storing the input array of words. The main logic resides in the f(pref, suff) method. This method iterates through the words array in reverse order, from the last element to the first. We iterate backwards because the problem requires us to return the largest index if multiple words match. For each word, we check two conditions: if it starts with the given pref and if it ends with the given suff. The built-in startsWith() and endsWith() string methods are used for this. The first word (while iterating backwards) that satisfies both conditions is the desired answer, and its index is returned immediately. If the loop finishes without finding any such word, it implies no word in the dictionary meets the criteria, and we return -1.

class WordFilter {    String[] words;     public WordFilter(String[] words) {        this.words = words;    }     public int f(String pref, String suff) {        for (int i = words.length - 1; i >= 0; i--) {            if (words[i].startsWith(pref) && words[i].endsWith(suff)) {                return i;            }        }        return -1;    }}

Complexity

Time

Constructor: O(1). `f` method: O(N * L) for each call, where N is the number of words and L is the maximum length of a word. The string matching operations `startsWith` and `endsWith` can take up to O(L) time. For Q queries, the total time complexity is O(Q * N * L).

Space

O(N * L), where N is the number of words and L is the maximum length of a word. This space is used to store the dictionary of words itself.

Trade-offs

Pros

  • Simple to understand and implement.

  • Low memory overhead, as it only stores the original list of words.

Cons

  • Very slow for a large number of queries, as each query requires a full scan of the dictionary.

  • Likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.

Solutions

class Trie { Trie [] children = new Trie [ 26 ]; List < Integer > indexes = new ArrayList <>(); void insert ( String word , int i ) { Trie node = this ; for ( char c : word . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; node . indexes . add ( i ); } } List < Integer > search ( String pref ) { Trie node = this ; for ( char c : pref . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { return Collections . emptyList (); } node = node . children [ c ]; } return node . indexes ; } } class WordFilter { private Trie p = new Trie (); private Trie s = new Trie (); public WordFilter ( String [] words ) { for ( int i = 0 ; i < words . length ; ++ i ) { String w = words [ i ]; p . insert ( w , i ); s . insert ( new StringBuilder ( w ). reverse (). toString (), i ); } } public int f ( String pref , String suff ) { suff = new StringBuilder ( suff ). reverse (). toString (); List < Integer > a = p . search ( pref ); List < Integer > b = s . search ( suff ); if ( a . isEmpty () || b . isEmpty ()) { return - 1 ; } int i = a . size () - 1 , j = b . size () - 1 ; while ( i >= 0 && j >= 0 ) { int c = a . get ( i ), d = b . get ( j ); if ( c == d ) { return c ; } if ( c > d ) { -- i ; } else { -- j ; } } return - 1 ; } } /** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(pref,suff); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem