Can anyone pass test using Python


  • 0
    L

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


  • 1
    I

    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

  • 0
    G

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


  • 0
    L
    This post is deleted!

  • 0
    J

    very understandable code


  • 0
    S
    This post is deleted!

  • 0
    L

    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;

Log in to reply
 

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