Java实现 LeetCode 745 前缀和后缀搜索（使用Hash代替字典树）

r囧r小猫 2023-07-25 12:56 2阅读 0赞

## 745. 前缀和后缀搜索 ##

给定多个 words，words\[i\] 的权重为 i 。

设计一个类 WordFilter 实现函数WordFilter.f(String prefix, String suffix)。这个函数将返回具有前缀 prefix 和后缀suffix 的词的最大权重。如果没有这样的词，返回 -1。

例子:

输入:  
WordFilter(\[“apple”\])  
WordFilter.f(“a”, “e”) // 返回 0  
WordFilter.f(“b”, “”) // 返回 -1  
注意:

words的长度在\[1, 15000\]之间。  
对于每个测试用例，最多会有words.length次对WordFilter.f的调用。  
words\[i\]的长度在\[1, 10\]之间。  
prefix, suffix的长度在\[0, 10\]之前。  
words\[i\]和prefix, suffix只包含小写字母。

class WordFilter { 
    
         HashMap<String, List<Integer>> prefMap = new HashMap<>();
            HashMap<String, List<Integer>> suffMap = new HashMap<>();
            String[] words;
    
            void addToPref(String word, int idx) { 
                int wlen = word.length();
                for (int i = 1; i <= wlen; i++) { 
                    prefMap.computeIfAbsent(word.substring(0, i), k -> new ArrayList<>()).add(idx);
                }
            }
    
            void addToSuff(String word, int idx) { 
                int wlen = word.length();
                for (int i = 0; i < wlen; i++) { 
                    suffMap.computeIfAbsent(word.substring(i), k -> new ArrayList<>()).add(idx);
                }
            }
    
            public WordFilter(String[] words) { 
                int size = words.length;
                this.words = words;
                for (int i = 0; i < size; i++) { 
                    addToPref(words[i], i);
                    addToSuff(words[i], i);
                }
            }
    
            public int f(String prefix, String suffix) { 
                List<Integer> l1 = prefMap.get(prefix);
                List<Integer> l2 = suffMap.get(suffix);
                if (prefix.length() == 0 || suffix.length() == 0) { 
                    if (prefix.length() == 0 && suffix.length() == 0) { 
                        return words.length-1;
                    }
                    if (prefix.length() == 0) { 
                        return l2 == null ? -1 : l2.get(l2.size()-1);
                    }
                    return l1 == null ? -1 : l1.get(l1.size()-1);
                }
                if (l1 == null || l2 == null) return -1;
                int idx1 = l1.size()-1;
                int idx2 = l2.size()-1;
                while (idx1 >= 0 && idx2 >= 0) { 
                    int i1 = l1.get(idx1);
                    int i2 = l2.get(idx2);
                    if (i1 == i2) return i1;
                    if (i1 < i2)
                        idx2--;
                    else idx1--;
                }
                return -1;
            }
    }
    
    /** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(prefix,suffix); */