32.串联所有单词的子串

题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

示例 1:

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

思路

方法一，从头到尾遍历s

words中每个字符的长度是m、words整个数组的长度是n
那我们每次可以从s中从头开始去遍历，每次是取 m*n 个字符(窗口)
然后把这个m*n个字符按照words中每个字符的长度m进行分割，然后把分割后的单词与words中的单词进行比较
如果和words中的都一样，那当前的索引就是。否则不是
在与words中的单词进行比较的时候，这个时候是不用关心顺序的，所以我们可以用一个哈希表来表示单词以及频次
- 当窗口中出现一个单词时，我们就把该单词加到哈希表中，如果已经存在，那就在后面的值+1
- 然后用哈希表中的内容与words中的单词进行对比，如果words中出现一个单词且也在哈希表中，那就将哈希表中该单词的频次减1，如果是0了就一次该单词
- 等到最后都遍历完，如果哈希表的长度是0，那就说明完全与words重点额一样


class Solution:

    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        if len(s) == 0 or len(words) == 0 or len(words[0]) == 0:
            return[]

        wordsLength = len(words[0])
        slideLength = wordsLength * len(words)
        wordsCount = len(words)

        wordsMap = dict()
        for word in words:
            wordsMap[word] = wordsMap.get(word, 0) + 1

        tempMap = dict()
        for index in range(len(s) - slideLength + 1):
            currentString = s[index: index+slideLength]
            print(currentString)
            for currentStringIndex in range(wordsCount):
                currentWord = currentString[currentStringIndex * wordsLength: (currentStringIndex + 1) * wordsLength]
                tempMap[currentWord] = tempMap.get(currentWord, 0) + 1

            print(tempMap)
            print(wordsMap)
            if tempMap == wordsMap:
                res.append(index)
            tempMap.clear()


        return res

时间复杂度：O(n×m×k)，n为s的长度，m为每个words中单词的长度，也就是len(words[0])，k为words的长度，也就是len(words)

空间复杂度：每次循环都新建一个字典tempMap，但循环结束就清除，所以空间为O(m)（m是words中不同单词的个数）？实际上每次循环都重新统计，所以空间上是O(m)，但要注意，我们每次循环都重新统计整个子串，所以没有利用滑动窗口的特性。

而下面方法二的时间复杂度是： - O(n×k): n为s的长度，k为words中单词的个数

方法二

上面方法一种当仅使用一个从0开始的滑动窗口时，为了避免漏掉一些子串，在缩短窗口时，每次只能缩小一格，而且这还会导致窗口内所维护的单词计数无效。那么，希望有一个方法，可以保证:
- 不遗漏子串 - 缩小窗口时，不会使窗口内的单词计数无效

那么，在使用滑动窗口时，每次都移动 sz = len(words[0]) 个字符，那么我们就可以按照单词的纬度进行统计。但是，这样会导致某一些子串没有枚举到（即[1, sz-1]为起点的子串都被忽略了），所以为了保证不遗漏子串，可以枚举以[0, sz-1]为起点的所有滑动窗口，并且每一个滑窗都是互相独立的。

建立滑动窗口
- 如何建立：计算窗口长度为：words中所有串拼接后的长度len，第一个窗口为[0,len-1]。
- 如果窗口中的字符串和words中所有串拼接后相等，则说明满足要求。
- 如何判断:
  - 将words中的所有word放入hashmap。key为word，value为个数。
  - 对窗口进行substr操作，每隔d，substr一次。d为words中word的长度。将substr的结果作为key放入另一个hashmap,个数为value。
  - 当窗口中没有剩余字符时，对两个map进行判断，如果相等。说明满足要求。此时记录窗口的起点。
建立多起点的滑动窗口。
- 何为多起点：
  - 一般理解滑动窗口从0或者某个数值开始，向右滑动不断滑动一个步长。
  - 此处需要建立多个滑动窗口，数量为d。起点分别为0,1,2...d；
- 为何需要多起点：
  - 如果只建立一个滑动窗口，那么每次就只能滑动一格，因为需要找到所有的可能。但是这样的操作意味着之前建立的map需要重新构建
  - 例如：foobarfoobar [foo][bar]。当foobar完成匹配后，向右滑动一格，oobarf。这时候需要重新构建map。插入oob ,arf。时间复杂度很高，而滑动窗口应该是线性时间复杂度，
  - 理想状态是，滑动d格，删去左侧foo，加入右侧foo。这个时候不需要重新构建map，map中原本的foo的计数先-1再+1即可，然后判断即可。

那么如果按照上面的方法，每次都滑动d，又会漏检。例如afoobarfoobar [foo][bar]

因此，需要多起点，afoobar，foobar。。个数为d个。这样每个窗口每次都是滑动d格。map的效率最高

- 如何建立多起点

- 从0开始初始化d个滑动窗口。每个滑动窗口每次都是滑动d格。建立相应的map。

- 最后得到vector<map<string, int>>;

滑动
- 由于已经建立了多起点的滑动窗口，所以不会存在漏检的情况。同时map的效率最高。

class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        val result = mutableListOf<Int>()
        // 边界：空串或空卡片直接返回
        if (s.isEmpty() || words.isEmpty()) {
            return result
        }

        // 每个单词的长度
        val wordLen = words[0].length
        // 单词个数总数
        val wordsCount = words.size
        // 窗口总长度
        val totalLen = wordLen * wordsCount
        // s 比答案还短，不可能有解
        if (s.length < totalLen) {
            return result
        }

        // 用HashMap记录匹配words中的个数和出现的次数
        val need = HashMap<String, Int>()
        for (w in words) {
            need[w] = need.getOrDefault(w, 0) + 1
        }

        // ---- 多个滑动窗口起点: 只需开 wordLen 条「车道」（偏移量）----
        for (offset in 0 until wordLen) {
            // 窗口左边界（对齐到单词）
            var left = offset
            // 窗口右边界
            var right = offset
            // 窗口内已纳入的合法单词数
            var count = 0
            // 窗口内的词频
            val window = HashMap<String, Int>()

            // right 每次读入一整张卡片，需保证能切出完整单词
            while (right + wordLen <= s.length) {
                // 取出 right 处的一张卡片，right 跳过它
                val word = s.substring(right, right + wordLen)
                right += wordLen

                if (!need.containsKey(word)) {
                    // 情况 A：假卡片（不在账本里）→ 整个窗口作废，从 right 重开
                    window.clear()
                    count = 0
                    left = right
                } else {
                    // 是正经卡片 → 入窗记账
                    window[word] = window.getOrDefault(word, 0) + 1
                    count++

                    // 虽然有这个卡但是这张卡片超量了 → 从队头不断踢，直到它降回合法数量
                    while (window[word]!! > need[word]!!) {
                        val leftWord = s.substring(left, left + wordLen)
                        window[leftWord] = window[leftWord]!! - 1
                        left += wordLen
                        count--
                    }

                    // 恰好凑齐一整副 → 命中！记下起点
                    if (count == wordsCount) {
                        result.add(left)
                        // 放走最左边那张卡，让窗口继续往后找下一个答案
                        val leftWord = s.substring(left, left + wordLen)
                        window[leftWord] = window[leftWord]!! - 1
                        left += wordLen
                        count--
                    }
                }
            }
        }
        return result
    }
}


class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 记录所有满足的结果索引
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }

        HashMap<String, Integer> map = new HashMap<>();
        // 每个单词的长度是固定的
        int one_word = words[0].length();
        int word_num = words.length;
        // 窗口长度
        int all_len = one_word * word_num;
        // 把words中的内容和次数都记录到HashMap中
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < one_word; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> tmp_map = new HashMap<>();
            while (right + one_word <= s.length()) {
                String w = s.substring(right, right + one_word);
                right += one_word;
                if (!map.containsKey(w)) {
                    count = 0;
                    left = right;
                    tmp_map.clear();
                } else {
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                    count++;
                    while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
                        String t_w = s.substring(left, left + one_word);
                        count--;
                        tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
                        left += one_word;
                    }
                    if (count == word_num) res.add(left);
                }
            }
        }
        return res;
    }
}

下一题

邮箱：charon.chui@gmail.com
Good Luck!