substring-with-concatenation-of-all-words

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

Example 1:

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

Input:
  s = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

My first try:
class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if s=="":
            return []
        if len(words)==0:
            return []
        combine_list=self.build_substring(words)
        example=combine_list[0]
        if len(example)>len(s):
            return []
        record_list=[]
        for i in range(len(s)-len(example)+1):
            for j in range(len(combine_list)):
                tmp_str=combine_list[j]
                if s[i:i+len(example)]==tmp_str and i not in record_list:
                    record_list.append(i)
        return record_list
        
    def build_substring(self,words):
        if len(words)==1:
            return words
        result_list=[]
        for i in range(len(words)):
            start=words[i]
            tmp_word=words.copy()
            tmp_word.remove(start)
            result=self.build_substring(tmp_word)
            for j in range(len(result)):
                result[j]=start+result[j]#Str concencating
                result_list.append(result[j])
        return result_list
#It can be solved but in exp time.
My code:
import numpy as np
class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if s=="":
            return []
        if len(words)==0:
            return []
        match_record=[]
        length=1000
        for item in words:
            if length>len(item):
                length=len(item)
        match_flag=True
        record_list=[]
        tmp_dict={}
        belong_dict={}
        for count in range(len(words)):
            tmp_list=[]
            for i in range(len(s)-length+1):
                if i+len(words[count])-1<len(s):
                    if s[i:i+len(words[count])]==words[count]:
                        tmp_list.append(i)
                        tmp_dict[i]=len(words[count])
                        if i not in belong_dict.keys():
                            belong_dict[i]=count
                        else:
                            #print('now check words index %d, s index %d'%(count,i))
                            #print(belong_dict[i])
                            if type(belong_dict[i])==list:
                                belong_dict[i].append(count)
                            else:
                                tmp_list1=[]
                                tmp_list1.append(belong_dict[i])
                                tmp_list1.append(count)
                                belong_dict[i]=tmp_list1
                                #print(belong_dict[i])
                
            match_record.append(tmp_list)
            if len(tmp_list)==0:
                match_flag=False
        if match_flag==False:
            return []
        print(belong_dict)
        print(tmp_dict)
        for i,item in enumerate(match_record):
            for j in range(len(item)):
                #print('checked %d match in %d words'%(j,i))
                count_tmp=0
                start=item[j]
                real_start=start
                #print('starting index %d'%start)
                while start in tmp_dict.keys():
                    start=start+tmp_dict[start]
                    count_tmp+=1
                    if count_tmp==len(words):
                        break
                #Simple check if this the case
                
                if count_tmp==len(words):
                    #print('found one, start checking')
                    marked=np.zeros(len(words))
                    count_mark=0
                    mark_flag=True
                    break_flag=False
                    start=real_start
                    count_tmp=0
                    while start in tmp_dict.keys():
                        if type(belong_dict[start])==list:
                            find_no_mark=False
                            for new_index in belong_dict[start]:
                                if marked[new_index]==0:
                                    marked[new_index]=1
                                    count_mark+=1
                                    find_no_mark=True
                                    break
                            if find_no_mark==False:
                                mark_flag=False
                                break_flag=True
                        else:
                            #print('belong index %d, mark status %d'%(belong_dict[start],marked[belong_dict[start]]))
                            if marked[belong_dict[start]]==0:
                                marked[belong_dict[start]]=1
                                count_mark+=1
                            else:
                                mark_flag=False
                                break_flag=True 
                        if break_flag:
                            break
                        start=start+tmp_dict[start]
                        count_tmp+=1
                        if count_tmp==len(words):
                            break
                    if mark_flag==False:
                        continue
                    if count_mark==len(words):
                        if item[j] not in record_list:
                            record_list.append(item[j])
                        
        return record_list
It can work, but python hhh  time limit