【刷题记录】30. 串联所有单词的子串

一、题目描述

来源：力扣（LeetCode）

给定一个字符串 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] 由小写英文字母组成

二丶思路分析

哈希表 + 滑动窗口实现

在【刷题记录】3. 无重复字符的最长子串中我们时候滑动窗口来实现过寻找最长子串。

假设

• 字符串 s的长度为 length
• words中的单词个数为 m，每个单词长度为 n
• 我们保持一个长度为 m*n 的窗口在字符串s上进行滑动，每次滑动的步长为 n(因为每个单词的长度是相同的，这样，每次滑动便不用重新计算窗口内的单词，因为每次窗口滑动的步长为 n,直接跨过了整个单词
• 使用哈希表 map 记录 words 中每个单词的出现次数
• 使用哈希表 cur统计窗口内子串 sub 每个单词的出现次数（每隔 n 长度作为一个单词）
• 移动窗口,如果这个窗口内一旦出现不存在map中的单词，或者这个单词在子串中出现的次数已经等于map中的次数这个滑动窗口就不符合要求，直接进入下一个滑动窗口的匹配
• 如果完全匹配上，则把滑动窗口的起始索引加入结果res中

三、代码实现

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> map = new HashMap<>();
        // 统计 words 中「每个目标单词」的出现次数
for(String word : words){
            map.put(word, map.getOrDefault(word, 0) +1);
        }
        int length = s.length();
        int m = words.length;
        int n = words[0].length();
        List<Integer> res = new ArrayList<>();
for(int i =0; i < length - m * n +1; i++){
            Map<String, Integer> cur = new HashMap<>();
            int index = i;
while(index < i + m * n){
                String curWord = s.substring(index, index + n);
if(!map.containsKey(curWord) || cur.get(curWord) == map.get(curWord)){
                    break;
                }
                cur.put(curWord, cur.getOrDefault(curWord, 0) +1);
                index += n;
            }
if(index == i + m * n){
                res.add(i);
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：
  网络异常，图片无法展示

  |
  ，n为字符串长度，m为单词个数
• 空间复杂度：
  网络异常，图片无法展示

  |

运行结果

总结

这道题目也是算利用滑动窗口思想来解决的题型中的一种。

在这个基础上我们来记录对比目标的work和窗口内的，看是否能够满足我们要求

继续加油~~