力扣30题解析：串联所有单词子串的Python实现方法

给定一个字符串 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"] 顺序排列的连接。

 思路如下:

对于这道题,很明显用滑动窗口来做,定义两个指针,判断指针对应字符是否满足条件即可

 判断如何满足条件:

      创建words的副本s1,建立循环,每次判断一个单词长度的字符串,若该字符串在s1里,则s1拿出该字符串,遍历循环,只需判断s1是否为空即可判断此时的字符串是否满足,将此时下标放入列表l中

如果大家按照此思路做,会发现时间复杂度非常高,为什么呢?相当于我每次都会去判断一次,每次只挪动一个下标,如果s非常长,加上words单词非常多,则花费非常多时间,所以在以上基础上再做一些完善:

     我们先定义一个sss[]数组,长度为len(s),每个都初始化为0,这个数组表示该下标对应字符串是否满足条件,满足的话修改为1

      对于一个需要判断的字符串,如果sss[i-len(words[0])] = 1,我们只需判断后面加入的长度为word[0]的字符串和s[i-len(word[0]):i]是否相同,若相同,设置sss[i] = 1

      举个例子,假设s = "abcdefabcd"'如上面,words = ["ab","cd","ef"],那么对于i = 2来说,因为此时i = 0是满足条件的,所以对于cdefab来说,只需判断ab和s[0:2]的字符串是否相等即可,当然需注意在i>=一个单词长度才开始进行这个判断

代码如下:

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        l = []
        if len(s) < len(words[0])*len(words):
            return []
        i = 0
        m = ''
        q = len(words[0])
        sss = [0 for i in range(len(s))]
        while i <= len(s)-len(words[0])*len(words):
            s1 = s[i:len(words[0])*len(words)+i]
            if i >= q and sss[i-q] == 1:
                m = s[i-q:i]
                n = s[len(words[0])*len(words)+i-len(words[0]):len(words[0])*len(words)+i]
                if m == n:
                    l.append(i)
                    sss[i] = 1
                    i += 1
                    continue
            ss = words.copy()
            k = 0
            for j in range(0,len(words)):
                w = s1[k:k+q]
                k += q
                if w in ss:
                    ss.pop(ss.index(w))
            if ss == []:
                sss[i] = 1
                l.append(i)
            i += 1
        return l

作者：三月@@