Prefix and Suffix Search

HardStringstrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Implement WordFilter(words), which indexes a list of words so that combined prefix-and-suffix lookups are fast. f(pref, suff) returns the **largest index** i such that words[i] starts with pref and ends with suff, or -1 if no word does. The prefix and the suffix may overlap inside the word, and each may equal the entire word. The list may contain duplicate words; the later index wins. Words are short (at most 7 letters) but there can be many words and many queries, so precomputation is worthwhile.

Examples

Input: ["WordFilter","f","f","f","f"] [[["apple","ample","apply"]],["a","e"],["app","y"],["ap","le"],["b","e"]]
Output: [null,1,2,0,-1]
"apple" (0) and "ample" (1) both fit "a...e"; the larger index is 1. Only "apply" fits "app...y". Only "apple" fits "ap...le". Nothing starts with "b".
Input: ["WordFilter","f","f","f","f"] [[["ab","ab","b"]],["a","b"],["b","b"],["ab","ab"],["abc","c"]]
Output: [null,1,2,1,-1]
Both copies of "ab" match, so index 1 wins. "b" is its own prefix and suffix. A prefix longer than every word cannot match.

Constraints

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 7
  • 1 <= pref.length, suff.length <= 7
  • All strings consist of lowercase English letters
  • At most 10^4 calls to `f`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems