745. Prefix and Suffix Search

Posted on | In |

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:

WordFilter([“apple”])

WordFilter.f(“a”, “e”) // returns 0

WordFilter.f(“b”, “”) // returns -1

Note:
words has length in range [1, 15000].

For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].

prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

代码

hashtable的思想
o(nL^3) 枚举所有单词的前缀后缀 key->word_index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class WordFilter {
public:
      unordered_map<string,int> dict;
    WordFilter(vector<string> words) {
         int index=0;
        for(auto word:words){
            int l=word.length();
            vector<string> prefix(l+1,"");
            vector<string> suffix(l+1,"");            
            for(int i=1;i<=l;i++){
               // for(int j=1;j<=l;j++){ 生成的前缀后缀字符串是笛卡尔乘积 
                    prefix[i]=prefix[i-1]+word[i-1];
                    suffix[i]=word[l-i]+suffix[i-1];
            }
//                       for(string t1:prefix){
//                           for(string t2:suffix)
//                           {
                              
//                                 dict[t1+'_'+t2]=index;
//                           }
                          
//                       }         
                for(int i=0;i<=l;i++)
                for(int j=0;j<=l;j++)
                {
                    string key=prefix[i]+'_'+suffix[j];
                        dict[key]=index;
                }  
                    
            index++;
        }
    }
    int f(string prefix, string suffix) {
        string key=prefix+"_"+suffix;
        auto it=dict.find(key);
        if(it!=dict.end()) return it->second;
         return -1;
    }
  
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */