• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

745. Prefix and Suffix Search

开发技术 开发技术 2周前 (05-02) 8次浏览

Design a special dictionary which has some words and allows you to search the words in it by a prefix and a suffix.

Implement the WordFilter class:

  • WordFilter(string[] words) Initializes the object with the words in the dictionary.
  • f(string prefix, string suffix) Returns the index of the word in the dictionary which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

 

Example 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]

Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".

 

Constraints:

  • 1 <= words.length <= 15000
  • 1 <= words[i].length <= 10
  • 1 <= prefix.length, suffix.length <= 10
  • words[i]prefix and suffix consist of lower-case English letters only.
  • At most 15000 calls will be made to the function f.

https://leetcode.com/problems/prefix-and-suffix-search/discuss/110044/Three-ways-to-solve-this-problem-in-Java

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

    public WordFilter(String[] words) {
        for(int w = 0; w < words.length; w++){
            for(int i = 0;  i <= words[w].length(); i++){
                for(int j = 0;  j <= words[w].length(); j++){
                    map.put(words[w].substring(0, i) + "#" + words[w].substring(words[w].length()-j), w);
                }
            }
        }
    }

    public int f(String prefix, String suffix) {
        return (map.containsKey(prefix + "#" + suffix))? map.get(prefix + "#" + suffix) : -1;
    }
}

组合,把每个单词用prefix和suffix组合成新的单词,用#隔开,从头到尾,这样最后返回的就是最大的。

class WordFilter {

    Map<String, List<Integer>> premap;
    Map<String, List<Integer>> sufmap;
    public WordFilter(String[] words) {
        premap = new HashMap();
        sufmap = new HashMap();
        for(int w = 0; w < words.length; w++) {
            for(int i = 0; i <= words[w].length(); i++) {
                String s = words[w].substring(0, i);
                if(!premap.containsKey(s)) premap.put(s, new ArrayList());
                premap.get(s).add(w);
            }
            for(int i = words[w].length(); i >= 0; i--) {
                String s = words[w].substring(i);
                if(!sufmap.containsKey(s)) sufmap.put(s, new ArrayList());
                sufmap.get(s).add(w);
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        if(!premap.containsKey(prefix) || !sufmap.containsKey(suffix)) return -1;
        List<Integer> p = premap.get(prefix);
        List<Integer> s = sufmap.get(suffix);
        int i = p.size()-1, j = s.size()-1;
        while(i >= 0 && j >= 0){
            if(p.get(i) < s.get(j)) j--;
            else if(p.get(i) > s.get(j)) i--;
            else return p.get(i);
        }
        return -1;
    }
}

两个map,一个存prefix和weight,一个存suffix和weight。map的value是一个存weight的list,这样相当于排了序,拥有此pre/suffix的权重值从小到大。

在f方法中,先把这个prefix和suffix对应的list拿出来,然后从后往前比较,如果这两个value相等说明weight相等,说明对应的是同一个word,返回这个weight。否则根据大小往前挪


程序员灯塔
转载请注明原文链接:745. Prefix and Suffix Search
喜欢 (0)