0745. Prefix and Suffix Search - kumaeki/LeetCode GitHub Wiki

0745. Prefix and Suffix Search

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.

解法1

先用最简单最直接的算法,用String的startsWith 和endsWith来依次处理.

果然超时了.

class WordFilter {

    String[] words;
    
    public WordFilter(String[] words) {
        this.words = words;
    }
    
    public int f(String prefix, String suffix) {
        int res = -1;
        for(int i = words.length - 1; i >= 0; i--){
            if(words[i].startsWith(prefix) && words[i].endsWith(suffix))
                return i;
        }
        return res;
    }
}

解法2

在初始化的时候,将所有的组合可能性先存入一个map, 然后查找的时候可以直接找到.

class WordFilter {

    Map<String, Integer> map = new HashMap<String, Integer>();
    
    public WordFilter(String[] words) {
        // 对于每一个word
        for(int k = 0; k < words.length; k++){
            String word = words[k];
            int len = word.length();
            // 找到所有前缀和后缀的组合,放入map中, 如果已存在,覆盖旧值
            // 因为是从位置0开始计算,所以map中最后留下的值就是可能组合的位置最大值
            for(int i = 0; i <= len; i++)
                for(int j = 0; j <= len; j++)
                    map.put(word.substring(0, i) + "#" + word.substring(len - j), k);
        }
    }
    
    public int f(String prefix, String suffix) {
        return map.getOrDefault(prefix + "#" + suffix, -1);
    }
}

解法3

在解法2中,对于每一个word,初始化时在map中保存了所有了preffix和suffix的组合.这样使得初始化较慢,但是查找变快. 在查找操作比初始化操作多很多的时候是更有效率的

查找操作没有那么多的情况下,可以用两个map来分表保存preffix的组合和suffix的组合. 这样查找会变慢一些,但是所需的储存空间会少一些.

class WordFilter {

    // 前缀map
    Map<String, List<Integer>> mapPre = new HashMap<String, List<Integer>>();
    // 后缀map
    Map<String, List<Integer>> mapSu = new HashMap<String, List<Integer>>();
    
    public WordFilter(String[] words) {
        // 对于每一个word
        for(int k = 0; k < words.length; k++){
            String word = words[k];
            int len = word.length();
            // 找到当前word所有可能的前缀,并把其对应的位置值k放入map中的list
            for(int i = 0; i <= len; i++){
                String str = word.substring(0, i);
                if(!mapPre.containsKey(word.substring(0, i)))
                    mapPre.put(str, new ArrayList<Integer>());
                mapPre.get(str).add(k);
            }
                
            
            // 找到当前word所有可能的后缀,并把其对应的位置值k放入map中的list
            for(int i = 0; i <= len; i++){
                String str = word.substring(len - i);
                if(!mapSu.containsKey(str))
                    mapSu.put(str, new ArrayList<Integer>());
                mapSu.get(str).add(k);
            }
        }
            
    }
    
    public int f(String prefix, String suffix) {
        // 如果有一个不存在,返回-1
        if(!mapPre.containsKey(prefix) || !mapSu.containsKey(suffix))
            return -1;
        
        // 遍历mapPre和mapSu中找到的前缀和后缀对应的位置list, 当位置相等时即找到满足条件的字符串
        List<Integer> list1 = mapPre.get(prefix), list2 = mapSu.get(suffix);
        int i = list1.size() - 1, j = list2.size() - 1;
        while(i >= 0 && j >= 0){
            if(list1.get(i) < list2.get(j))
                j--;
            else if(list1.get(i) > list2.get(j))
                i--;
            else
                return list1.get(i);
        }
        
        return -1;
    }
}
⚠️ **GitHub.com Fallback** ⚠️