Prefix and Suffix Search

Problem

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.

Examples

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.

Solution

Method 1 – Hash Map Preprocessing

Intuition

To efficiently answer prefix and suffix queries, we can preprocess all possible prefix and suffix combinations for each word and store their largest index in a hash map. This allows for constant time lookups during queries.

Approach

1. For each word, generate all possible prefix and suffix pairs.
2. Store each (prefix, suffix) pair in a hash map with the word's index.
3. For queries, look up the (prefix, suffix) pair in the hash map and return the stored index, or -1 if not found.

Code

C++

class WordFilter {
    unordered_map<string, int> mp;
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            string w = words[i];
            for (int p = 1; p <= w.size(); ++p) {
                string pref = w.substr(0, p);
                for (int s = 0; s <= w.size(); ++s) {
                    string suff = w.substr(w.size() - s, s);
                    mp[pref + '#' + suff] = i;
                }
            }
        }
    }
    int f(string pref, string suff) {
        string key = pref + '#' + suff;
        return mp.count(key) ? mp[key] : -1;
    }
};

Go

type WordFilter struct {
    mp map[string]int
}

func Constructor(words []string) WordFilter {
    mp := make(map[string]int)
    for i, w := range words {
        for p := 1; p <= len(w); p++ {
            pref := w[:p]
            for s := 0; s <= len(w); s++ {
                suff := w[len(w)-s:]
                mp[pref+"#"+suff] = i
            }
        }
    }
    return WordFilter{mp}
}

func (wf *WordFilter) F(pref string, suff string) int {
    key := pref + "#" + suff
    if v, ok := wf.mp[key]; ok {
        return v
    }
    return -1
}

Java

class WordFilter {
    Map<String, Integer> mp = new HashMap<>();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; ++i) {
            String w = words[i];
            for (int p = 1; p <= w.length(); ++p) {
                String pref = w.substring(0, p);
                for (int s = 0; s <= w.length(); ++s) {
                    String suff = w.substring(w.length() - s);
                    mp.put(pref + "#" + suff, i);
                }
            }
        }
    }
    public int f(String pref, String suff) {
        String key = pref + "#" + suff;
        return mp.getOrDefault(key, -1);
    }
}

Kotlin

class WordFilter(words: Array<String>) {
    private val mp = mutableMapOf<String, Int>()
    init {
        for ((i, w) in words.withIndex()) {
            for (p in 1..w.length) {
                val pref = w.substring(0, p)
                for (s in 0..w.length) {
                    val suff = w.substring(w.length - s)
                    mp["$pref#$suff"] = i
                }
            }
        }
    }
    fun f(pref: String, suff: String): Int = mp["$pref#$suff"] ?: -1
}

Python

class WordFilter:
    def __init__(self, words: list[str]) -> None:
        self.mp: dict[str, int] = {}
        for i, w in enumerate(words):
            for p in range(1, len(w)+1):
                pref = w[:p]
                for s in range(len(w)+1):
                    suff = w[len(w)-s:]
                    self.mp[f"{pref}#{suff}"] = i
    def f(self, pref: str, suff: str) -> int:
        return self.mp.get(f"{pref}#{suff}", -1)

Rust

use std::collections::HashMap;
struct WordFilter {
    mp: HashMap<String, i32>,
}
impl WordFilter {
    fn new(words: Vec<String>) -> Self {
        let mut mp = HashMap::new();
        for (i, w) in words.iter().enumerate() {
            for p in 1..=w.len() {
                let pref = &w[..p];
                for s in 0..=w.len() {
                    let suff = &w[w.len()-s..];
                    mp.insert(format!("{}#{}", pref, suff), i as i32);
                }
            }
        }
        WordFilter { mp }
    }
    fn f(&self, pref: &str, suff: &str) -> i32 {
        let key = format!("{}#{}", pref, suff);
        *self.mp.get(&key).unwrap_or(&-1)
    }
}

TypeScript

class WordFilter {
    private mp: Record<string, number> = {};
    constructor(words: string[]) {
        for (let i = 0; i < words.length; ++i) {
            const w = words[i];
            for (let p = 1; p <= w.length; ++p) {
                const pref = w.slice(0, p);
                for (let s = 0; s <= w.length; ++s) {
                    const suff = w.slice(w.length - s);
                    this.mp[`${pref}#${suff}`] = i;
                }
            }
        }
    }
    f(pref: string, suff: string): number {
        return this.mp[`${pref}#${suff}`] ?? -1;
    }
}

Complexity

• ⏰ Time complexity: O(N * L^2) for preprocessing, where N is number of words and L is max word length. Each word generates O(L^2) prefix-suffix pairs. Query is O(1).
• 🧺 Space complexity: O(N * L^2), storing all prefix-suffix pairs for all words.