The algorithm is window sliding like used by many others. Using collections.defaultdict eliminates the if-else conditional statements while checking new words:
class Solution: # @param S, a string # @param L, a list of string # @return a list of integer def findSubstring(self, S, L): if not L or not L: return None wl = len(L) totl = len(L) * wl count_tmpl = collections.defaultdict(int) for word in L: count_tmpl[word] += 1 rtn =  for i in range(wl): count = copy.copy(count_tmpl) j = i while j < len(S)-wl+1: count[S[j:j+wl]] -= 1 while count[S[j:j+wl]] < 0: count[S[i:i+wl]] += 1 i += wl j += wl if j-i == totl: rtn.append(i) return rtn
You can simply use collections.Counter() like this:
count_tmpl = Counter(L)
It has same operations than defaultdict(int) and more (like addition/ soustraction, union/ intersection between Counters)
it took me a while to understand this. You used i inside the for loop as the start of the sliding window. And I thought you want to increment i, but that's the sliding window start. Here is a modified version.
def findSubstring(self, s, words): """ :type s: str :type words: List[str] :rtype: List[int] """ res =  m,n,k = len(s), len(words), len(words) counter = collections.Counter(words) for i in xrange(k): temp = copy.deepcopy(counter) start = i for j in xrange(start, m-k+1, k): word = s[j:j+k] temp[word]-=1 while temp[word] < 0: temp[s[start:start+k]]+=1 start+=k if j+k-start==n*k: res.append(start) return res
Time Complexity: O(m). Space: O(m)