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

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);

 */

巴特西

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

745. 前缀和后缀搜索

最新文章

热门文章