745. Prefix and Suffix Search (Hard)

https://leetcode.com/problems/prefix-and-suffix-search/

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:

  1. words has length in range [1, 15000].
  2. For each test case, up to words.length queries WordFilter.f may be made.
  3. words[i] has length in range [1, 10].
  4. prefix, suffix have lengths in range [0, 10].
  5. words[i] and prefix, suffix queries consist of lowercase letters only.

 

Hints

Solutions

class WordFilter {
    Map<String, Integer> map = new HashMap<>();

    public WordFilter(String[] words) {
        int index = 0;
        for (String word : words) {
            int len = word.length();
            String[] prefixes = new String[len + 1];
            String[] suffixes = new String[len + 1];
            prefixes[0] = "";
            suffixes[0] = "";
            for (int i = 1; i <= len; i++) {
                prefixes[i] = prefixes[i - 1] + word.charAt(i - 1);
                suffixes[i] = word.charAt(len - i) + suffixes[i - 1];
            }

            for (String prefix : prefixes) {
                for (String suffix : suffixes) {
                    map.put(prefix + "_" + suffix, index);
                }
            }
            index++;
        }
    }

    public int f(String prefix, String suffix) {
        String key = prefix + "_" + suffix;
        if (map.containsKey(key)) {
            return map.get(key);
        } else {
            return -1;
        }
    }
}


/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-15 18:24:51

results matching ""

    No results matching ""