LeetCode 30. Concatenate substrings of all words

30. Concatenate the substrings of all words

 

【 violence + Hashtable 】 For each character , The length of the whole string can be formed from the beginning to the end , Each move words[i] The position of the length determines whether it is in the hash table .

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

【 The sliding window + Hash 】 We found that when a string does not match, we can jump to the position of the next string first , In this way, only the previous character is removed from the hash table .

class Solution {

    //  The sliding window + Hash  

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

Sure enough, it's much faster .