🌕🌕🌗 30. 串联所有单词的子串

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 思路：
        // 滑动窗口
        // 首先 map 记录 words 各单词及出现的频率
        // 窗口大小为 item * len
        // 每次的窗口滑动时，以 len 为单位进行滑动
        // 窗口初始下标，就必须是从 [0, len - 1] 开始，依次尝试，每次就是一个完整的滑动到末尾的过程
        int len = words.length;
        int single = words[0].length();
        int total = len * single;
        HashMap<String, Integer> map = new HashMap<>();
        for(String str : words) {
            if(!map.containsKey(str)) {
                map.put(str, 1);
            } else {
                int count = map.get(str);
                count ++;
                map.put(str, count);
            }
        }
        List<Integer> res = new ArrayList<>();
        int size = s.length();
        if(size < total) {
            return res;
        }
        // 依次从不同起始下标开始进行滑动窗口的遍历
        for(int i = 0; i < single; i ++) {
            int end = i + total; // 初始滑动窗口的右边界
            if(end > size) {
                break;
            }
            int left = i;
            int right = i + single; // 这里可以看出，右边界为开区间
            HashMap<String, Integer> tmpMap = new HashMap<>(); // 记录当前滑动窗口的字符串关系
            int count = 0; // 已经完全匹配的个数
            int ll = left;
            while(right <= end) {
                // 以 len 为单位进行选取
                String cur = s.substring(ll, right);
                if(map.containsKey(cur)) {
                    if(!tmpMap.containsKey(cur)) {
                        tmpMap.put(cur, 1);
                        count ++;
                    } else {
                        int fre = tmpMap.get(cur); 
                        fre ++; // 实际拥有的个数
                        tmpMap.put(cur, fre);
                        int mapCount = map.get(cur); // 期望拥有的个数
                        if(fre <= mapCount) {
                            count ++;
                        }
                    }
                }
                right += single;
                ll += single;
            }
            // 初始窗口形成
            if(count == len) {
                res.add(i);
            }
            right -= single;
            // System.out.println(right + "  " + count);
            // 向右滑动窗口，每次依旧滑动一个单词的长度
            while(right <= size - single) {
                String rv = s.substring(left, left + single); // 要移除的单词
                left += single; // 更新 left
                if(map.containsKey(rv)) { // map 有该字符，那么 tmpMap 中肯定也保存了
                    int mapCount = map.get(rv);
                    int fre = tmpMap.get(rv);
                    // 判断该单词去掉后，是否影响匹配的字符串的个数
                    if(fre <= mapCount) {
                        count --;
                    }
                    fre --;
                    if(fre == 0) {
                        tmpMap.remove(rv);
                    } else {
                        tmpMap.put(rv, fre);
                    }
                }
                String add = s.substring(right, right + single); // 新增的单词
                right += single; // 更新 right
                if(map.containsKey(add)) {
                    if(!tmpMap.containsKey(add)) {
                        tmpMap.put(add, 1);
                        count ++;
                    } else {
                        int fre = tmpMap.get(add);
                        fre ++;
                        tmpMap.put(add, fre);
                        int mapCount = map.get(add);
                        // 判断是否是多余单词
                        if(fre <= mapCount) {
                            count ++;
                        }
                    }
                }
                // System.out.println(left + "  " + rv + "  " + add + "  " + count);
                // 判断此时是否满足条件
                if(count == len) {
                    res.add(left);
                }
            }
        } 
        return res;
    }
}

---

输出