# Can anyone pass test using Python

• The Solution with time complexity len(S)*len(L) using java can easily pass test but not Python.

• I just passed this using Python, here is the AC'ed python code for your reference.

``````class Solution:
# @param S, a string
# @param L, a list of string
# @return a list of integer
def findSubstring(self, S, L):
""" The idea is very simple, use brute-force with hashing. First we compute the hash for each word given in L and add them up. Then we traverse from S[0] to S[len(S) - total_length], for each index, if the first substring in L, then we compute the total hash for that partition, if hashes match, then we have a match.
"""
if S is None or L is None or len(L) == 0:
return []
# the length of each word
len_of_word = len(L[0])
# the length of entire substring
total_length = len_of_word * len(L)
# use a set to reduce lookup time
word_set = set(L)
# total hash for the given list of words
target_hash = 0
for item in L:
target_hash += hash(item)
ret = []
for start in xrange(len(S) - total_length + 1):
if S[start:start+len_of_word] not in word_set:
continue
end = start + total_length - 1
test_hash = 0
for walker in xrange(start, end + 1, len_of_word):
substring = S[walker:walker + len_of_word]
# early termination if any of the substring not in set
if substring not in word_set:
break
test_hash += hash(substring)
if test_hash == target_hash:
ret.append(start)
return ret``````

• nice, an extension of rabin-karp implementation of strstr :)

• This post is deleted!

• very understandable code

• This post is deleted!

• My AC solution.

``````class Solution:
# @param S, a string
# @param L, a list of string
# @return a list of integer
def findSubstring(self, S, L):
def match(s,gap,hash):
newhash=dict();
k=0;
while(k<(len(s)//gap)):
sub=s[k*gap:(k+1)*gap];
if(sub in hash):
newhash.setdefault(sub,0);
newhash[sub]+=1;
else:
return False;
k+=1;

return newhash==hash;

if(len(L)==0):return [];
ret=[];
hash=dict();
for k in L:
hash.setdefault(k,0);
hash[k]+=1;
totalLen=len(L)*len(L[0]);

i=0;
while(i<=len(S)-totalLen):
if(match(S[i:i+totalLen],len(L[0]),dict(hash))):
ret.append(i);
i+=1;
return ret;``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.