LeetCode_滑动窗口_困难_30.串联所有单词的子串

冷不防 2023-10-06 18:38 94阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个字符串 s 和一些长度相同的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。  
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

**示例 1：**  
输入：s = “barfoothefoobarman”, words = \[“foo”,“bar”\]  
输出：\[0,9\]  
解释：  
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。  
输出的顺序不重要, \[9,0\] 也是有效答案。

**示例 2：**  
输入：s = “wordgoodgoodgoodbestword”, words = \[“word”,“good”,“best”,“word”\]  
输出：\[\]

**示例 3：**  
输入：s = “barfoofoobarthefoobarman”, words = \[“bar”,“foo”,“the”\]  
输出：\[6,9,12\]

**提示：**  
1 <= s.length <= 104  
s 由小写英文字母组成  
1 <= words.length <= 5000  
1 <= words\[i\].length <= 30  
words\[i\] 由小写英文字母组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

## 2.思路 ##

（1）暴力穷举法  
本思路是设 words 中所有单词串联形成的子串的长度为 totalLen，然后将字符串 s 中每个长度为 totalLen 的子串与 words 中的单词进行匹配，其具体步骤如下：

*  先定义需要用到的变量，例如保存结果的数组 res，每个单词的长度 wordLen，words 数组的长度 wordNum 等等，此外为了方便在遍历字符串 s 的子串时进行匹配，需定义一个 hashMap 来保存 words 中的单词，且键/值为字符串/出现的次数；
 *  开始遍历字符串中每个长度为 totalLen 的子串，在 while 循环中，先截取长度为 wordLen 的单词 subWord；
    
     *  如果 subWord 存在于 words 中，并且 tempMap 中的该单词的个数与words中的不相等（即 words 中还有多余的该单词可供匹配），则说明当前单词匹配成功，然后进行下一趟循环；
     *  否则，说明起始位置为i的子串与 words 中的单词不能完全匹配，退出循环，并且 i++，进行下一个子串的匹配；
 *  遍历子串结束后，返回 res 即可。

（2）滑动窗口  
思路参考[LeetCode用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public List<Integer> findSubstring(String s, String[] words) {
        
            List<Integer> res = new ArrayList<>();
            // wordLen: 每个单词的长度
            int wordLen = words[0].length();
            // wordNum: words 数组的长度
            int wordNum = words.length;
            //将 words 中的字符串保存到 HashMap 中，键/值:字符串/出现的次数
            Map<String, Integer> wordsMap = new HashMap<String, Integer>();
            for (String word : words) {
        
                wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
            }
            //遍历字符串中每个长度为 totalLen 的子串
            int totalLen = wordLen * wordNum;
            Map<String, Integer> tempMap = new HashMap<>();
            for (int i = 0; i < s.length() - totalLen + 1; i++) {
        
                int k = i;
                tempMap.clear();
                while (k < i + totalLen) {
        
                    //截取长度为 wordLen 的单词
                    String subWord = s.substring(k, k + wordLen);
                    //当前单词存在于 words 中，并且 tempMap 中的该单词的个数与 words 中的不相等(即 words 中还有多余的该单词可供匹配)
                    if (wordsMap.containsKey(subWord) && !wordsMap.get(subWord).equals(tempMap.get(subWord))) {
        
                        //将已经匹配成功的单词保存到 tempMap 中
                        tempMap.put(subWord, tempMap.getOrDefault(subWord, 0) + 1);
                        // k 向后移动 wordLen 个的单位长度
                        k += wordLen;
                    } else {
        
                        //出现不匹配的情况，立即退出循环
                        break;
                    }
                }
                //起始位置为 i 的子串与 words 中的单词完全匹配
                if (k == i + totalLen) {
        
                    res.add(i);
                }
            }
            return res;
        }
    }

//思路2————滑动窗口
    class Solution {
        
        public List<Integer> findSubstring(String s, String[] words) {
        
            List<Integer> res = new ArrayList<Integer>();
            int m = words.length;
            int n = words[0].length();
            int ls = s.length();
            for (int i = 0; i < n; i++) {
        
                if (i + m * n > ls) {
        
                    break;
                }
                Map<String, Integer> differ = new HashMap<String, Integer>();
                for (int j = 0; j < m; j++) {
        
                    String word = s.substring(i + j * n, i + (j + 1) * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                }
                for (String word : words) {
        
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
        
                        differ.remove(word);
                    }
                }
                for (int start = i; start < ls - m * n + 1; start += n) {
        
                    if (start != i) {
        
                        String word = s.substring(start + (m - 1) * n, start + m * n);
                        differ.put(word, differ.getOrDefault(word, 0) + 1);
                        if (differ.get(word) == 0) {
        
                            differ.remove(word);
                        }
                        word = s.substring(start - n, start);
                        differ.put(word, differ.getOrDefault(word, 0) - 1);
                        if (differ.get(word) == 0) {
        
                            differ.remove(word);
                        }
                    }
                    if (differ.isEmpty()) {
        
                        res.add(start);
                    }
                }
            }
            return res;
        }
    }

[LeetCode]: https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/30-chuan-lian-suo-you-dan-ci-de-zi-chuan-bvy9/