Leecode 30. Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

A problem of string processing. Care about details.

Solution 1:

# T:O(m*n*k) S:O(n*k)
class Solution:
    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        result, words, word_num, word_len = [], {}, len(L), len(L[0])
        for i in L:
            if i not in words:
                words[i] = 1
            else:
                words[i] += 1

        for i in xrange(len(S) + 1 - word_len * word_num):
            cur, j = {}, 0
            while j < word_num:
                word = S[i + j * word_len:i + j * word_len + word_len]
                if word not in words: 
                    break
                if word not in cur: 
                    cur[word] = 1
                else:
                    cur[word] += 1
                if cur[word] > words[word]:
                    break
                j += 1
            if j == word_num:
                result.append(i)
                
        return result

Run Time: 740 ms

Solution 2:

# T:O(m*n*k) S:O(n*k)
class Solution:
    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        n,m,w=len(S),len(L),len(L[0])
        rst=[]
        for index in xrange(n-m*w+1):
            seg=[S[i:i+w] for i in xrange(index,index+m*w,w)]
            for item in L:
                if item in seg:
                    seg.remove(item)
                else:
                    break
            if seg==[]:rst.append(index)
        return rst

Run Time: 524 ms