subject

745. Prefix and suffix search

Design a special dictionary that contains some words , And can retrieve words through prefixes and suffixes .

Realization WordFilter class ：

• WordFilter(string[] words) Use words in the dictionary words Initialize object .
• f(string pref, string suff) The return dictionary has a prefix prefix And suffixes suff The subscript of the word . If there is more than one subscript that meets the requirements , Return to it The largest subscript . If there is no such word , return -1 .

Example ：

 Input 
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
 Output 
[null, 0]
 explain 
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); //  return  0 , Because the index is zero  0  's words ： Prefix  prefix = "a"  And   suffix  suff = "e" .

Tips ：

• 1 <= words.length <= 104
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i]、pref and suff It's only made up of lowercase letters
• Up to function f perform 104 Secondary call

Ideas

• Save all pre suffix combinations in a dictionary , Access directly to the dictionary

Code

class WordFilter:

    def __init__(self, words: List[str]):
        self.dic = {
    }
        for i,word in enumerate(words):
            for pre in range(1,len(word)+1):
                for suff in range(1,len(word)+1):
                    self.dic[word[:pre] + "#" + word[-suff:]] = i
        

    def f(self, pref: str, suff: str) -> int:
        return self.dic.get(pref+"#"+suff,-1)

Complexity

• init
  • Time complexity ：$O(lengt{h}_{words}\ast lengt{h}_{word}^2)$
  • Spatial complexity ：$O(lengt{h}_{words}\ast lengt{h}_{word}^2)$
• f
  • Time complexity ：$O(1)$
  • Spatial complexity ：$O(1)$