(Hard) 30. Substring with Concatenation of All Words

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 104
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

思路:
先计算每次shift: 单词长度 x 单词量
依每次 shift 可组出 所有可能
再由每个可能出发
把 words中 与存在每个可能的 token(与单一单词长度一样)的element 依序扣除
最後
如果 words 长度为 0 则可加进 答案

Code:

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        shift=len(words)*len(words[0])
        wl=len(words[0])
        #print(shift)
        ansList = []
        cnt = 0 
        while cnt < len(s):
            if cnt+shift >len(s):
                break
            tmp = s[cnt:cnt+shift]
            tmp2 = tmp
            flag = 0
            #print(tmp2)
            '''
            for i in words:
                #if i not in tmp:
                #    flag = 1
                if i in tmp:
                    #tmp.remove(i)
                    #print(i)
                    rmv=tmp.replace(i,"",1)
                    #print(rmv)
                    tmp = rmv
                else:
                    flag = 1
                    break
            '''
            tw = words.copy()
            #print("tw",tw)
            j = 0
            while j < len(tmp):
                if tmp[j:j+wl] in tw:
                    try:
                        tw.remove(tmp[j:j+wl])
                    except:
                        #print("NoIN")
                        pass
                j =  j+wl
                
            #print(">>>",len(tw))        
            if len(tw)==0:
                ansList.append(cnt)
            #if  flag == 0:
            #    ansList.append(cnt)
            #print(tmp)
            cnt+=1
        #print(ansList) 
        return ansList
        

Result:
先不要
Status : AC
But : 时间/空间 复杂度 有很大进步空间