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

一时失言乱红尘 2022-10-31 04:26 116阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[大佬题解][Link 1]

//哈希表 + 双指针 + 滑动窗口
    class Solution {
        
        public List<Integer> findSubstring(String s, String[] words) {
        
            List<Integer> res = new ArrayList<Integer>();
            if(words.length == 0)
                return res;
            int n = s.length();
            int m = words.length;
            int w = words[0].length();
    
            Map<String, Integer> map = new HashMap<String, Integer>();
            for(String word : words){
        
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
    
            for(int i = 0; i < w; i++){
        
                Map<String, Integer> curMap = new HashMap<String, Integer>();
                for(int j = i; j + w <= n; j += w){
        
                    String cur = s.substring(j, j + w);
                    if(j >= i + m * w){
        
                        int idx = j - m * w;
                        String prev = s.substring(idx, idx + w);
                        if(curMap.get(prev) == 1)
                            curMap.remove(prev);
                        else
                            curMap.put(prev, curMap.get(prev) - 1);
                    }
                    curMap.put(cur, curMap.getOrDefault(cur, 0) + 1);
                    // 如果当前子串对应 map 和 words 中对应的 map 相同，说明当前子串包含了「所有的目标单词」，将起始下标假如结果集
                    if (map.containsKey(cur) && curMap.get(cur).equals(map.get(cur)) && cmp(map, curMap)) {
        
                        res.add(j - (m - 1) * w);
                    }
                }
            }
            return res;
        }
    
         // 比较两个 map 是否相同
        boolean cmp(Map<String, Integer> m1, Map<String, Integer> m2) {
        
            if (m1.size() != m2.size()) return false;
            for (String k1 : m1.keySet()) {
        
                if (!m2.containsKey(k1) || !m1.get(k1).equals(m2.get(k1))) return false;
            }
            for (String k2 : m2.keySet()) {
        
                if (!m1.containsKey(k2) || !m1.get(k2).equals(m2.get(k2))) return false;
            }
            return true;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/e0b19656faf24444addf392fe2f28d19.png
[Link 1]: https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/shua-chuan-lc-po-su-ha-xi-biao-jie-fa-hu-ml3x/