【LeetCode】 串联所有单词的子串（python）

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

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

输入：
s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]

解题思路：
1、由于words中所有子串长度相等（记为length），因此可以循环遍历s，如果s中 s[当前位置 i : 当前位置 i + length] 在words中，则创建words数组的拷贝temp，并移除temp中等于s[i : i + length]的子串：

		while i < len(s):
            if s[i: i + length] in words:
                j = i + length
                temp =  [ele for ele in words]
                temp.remove(s[i: i + length])

2、令 j = i + length，然后继续循环遍历s， 若s[j: j + length]在words中，则从temp中移除s[j: j + length]，否则令j=len(s)，跳出while循环：

			while j < len(s):
                    if s[j: j + length] in temp:
                        temp.remove(s[j: j + length])
                        j += length
                    else:
                        j = len(s)

3、最后，若temp数组为空，则将i添加到result数组中，并令i += 1，否则直接令i += 1:

				if len(temp) == 0:
                    result.append(i)
                    i += 1
                else:
                    i += 1

PS：本解题方法还存在很多可以改进的地方，因为执行用时太高了。

完整代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words or len(words) > len(s):
            return []
        result = []
        length = len(words[0])
        i = 0
        while i < len(s):
            if s[i: i + length] in words:
                j = i + length
                temp =  [ele for ele in words]
                temp.remove(s[i: i + length])
                while j < len(s):
                    if s[j: j + length] in temp:
                        temp.remove(s[j: j + length])
                        j += length
                    else:
                        j = len(s)
                if len(temp) == 0:
                    result.append(i)
                    i += 1
                else:
                    i += 1
            else:
                i += 1
        return result