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.

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        char = len(words[0])
        begin_idx = []
        i = 0
        while i <= len(s) - len(words) * char:
            tmp_words = list(words)
            if s[i:i+char] in tmp_words:
                tmp_words.remove(s[i:i+char])
        #         print(i,i+char)
                j = i+char
                while j <= len(s):
                    if s[j:j+char] in tmp_words:
                        tmp_words.remove(s[j:j+char])
                        j += char
                    else:
                        break
            if len(tmp_words) == 0:
                begin_idx.append(i)
            
            i += 1
        
        return begin_idx

- 성능이 좋지 못하다. discussion에 나온 다른 방법도 참고해봐야겠다..

Runtime: 1480 ms, faster than 23.33% of Python3 online submissions for Substring with Concatenation of All Words.

Memory Usage: 14.7 MB, less than 27.56% of Python3 online submissions for Substring with Concatenation of All Words.