LeetCode 30. 串联所有单词的子串

30. 串联所有单词的子串

 

【暴力+哈希表】对于每一个字符，都暴力遍历从他开始到一直到后面能组成整个字符串的长度，每次移动words[i]长度的位置就判断是否在哈希表中。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int m = words.length, n = words[0].length();
        Map<String, Integer> map = new HashMap();
        for(var str: words) map.put(str, map.getOrDefault(str, 0) + 1);
        int l = s.length() - m * n;
        List<Integer> ans = new ArrayList();
        for(var i = 0; i <= l; i++){
            Map<String, Integer> tab = new HashMap(map);
            int flag = 1;
            for(var j = 1; j <= m; j++){
                String tmp = s.substring(i + (j - 1) * n, i + j * n);
                if(tab.containsKey(tmp)) {
                    if(tab.get(tmp) == 1) tab.remove(tmp);
                    else tab.put(tmp, tab.get(tmp) - 1);
                }
                else{
                    flag = 0; break;
                }
            }
            if(flag == 1) ans.add(i);
        }
        return ans;
    }
}

【滑动窗口+哈希】我们发现当一个字符串不匹配的时候我们可以先跳到下一个字符串的位置，这样哈希表只去掉之前那一个字符就行。

class Solution {

    // 滑动窗口+哈希 

    public List<Integer> findSubstring(String s, String[] words) {
        int m = s.length(), n = words.length, l = m - n, k = words[0].length();
        Map<String, Integer> map = new HashMap();
        List<Integer> ans = new ArrayList();
        for(var str: words) map.put(str, map.getOrDefault(str, 0) + 1);
        for(var i = 0; i < k; i++){
            int j = i;
            Map<String, Integer> tmp = new HashMap();
            while(j + k * n <= m){
                // System.out.println(j);
                if(j == i){
                    for(var p = 0; p < n; p++){
                        var str = s.substring(j + p * k, j + (p + 1) * k);
                        tmp.put(str, tmp.getOrDefault(str, 0) + 1);
                    }
                    if(map.equals(tmp)) {
                        ans.add(j);
                    }
                    // tmp.forEach((x, y) -> {
                    //     System.out.print(x + " " + y + ", ");
                    // });
                    // System.out.println();
                }else{
                    var old = s.substring(j - k, j);
                    if(tmp.get(old) == 1) tmp.remove(old);
                    else tmp.put(old, tmp.getOrDefault(old, 0) - 1);
                    var neww = s.substring(j + (n - 1) * k, j + n * k);
                    tmp.put(neww, tmp.getOrDefault(neww, 0) + 1);
                    if(map.equals(tmp)) {
                        ans.add(j);
                    }
                    // tmp.forEach((x, y) -> {
                    //     System.out.print(x + " " + y + ", ");
                    // });
                    // System.out.println();
                }
                j += k;
            }
        }
        return ans;
    }
}

果然要快很多。