Python solution with two dict of counts


  • 1
    B
    class Solution:
        # @param S, a string
        # @param L, a list of string
        # @return a list of integer
        def findSubstring(self, S, L):
            if len(S) == 0 or len(L) == 0 or len(L[0]) == 0:
                return []
            
            words = {}
            for word in L:
                words[word] = 1 if word not in words else words[word] + 1
    
            l = len(L[0])
            ret = []
            for i in xrange(0, l):
                b = i
                curr = {}
                for j in xrange(i, len(S), l):
                    word = S[j:j+l]
                    if word in words:
                        if word not in curr:
                            curr[word] = 1
                        elif curr[word] < words[word]:
                            curr[word] += 1
                        else:
                            while S[b:b+l] != word:
                                b += l
                                curr[S[b:b+l]] -= 1
                                if curr[S[b:b+l]] == 0:
                                    del curr[S[b:b+l]]
                            b += l
                    else:
                        curr = {}
                        b = j + l
    
                    if sum(curr.values()) == len(L):
                        ret.append(b)
                        curr[S[b:b+l]] -= 1
                        if curr[S[b:b+l]] == 0:
                            del curr[S[b:b+l]]
                        b += l
            
            return ret
    

    use dict to save the count of words, because there will be duplicate words in L. can my code be more clean?


  • 1
    S

    You could move the dictionary update to a function:

       def _updateVars(self, S, b, l, curr):
            curr[S[b:b+l]] -= 1
            if curr[S[b:b+l]] == 0:
                del curr[S[b:b+l]]
            return curr
    

    This would result in :

                        else:
                        while S[b:b+l] != word:
                            b += l
                            curr = self._updateVars(S, b, l, curr)
    

    And

                    if sum(curr.values()) == len(L):
                    ret.append(b)
                    curr = self._updateVars(S, b, l, curr)
                    b += l
    

Log in to reply
 

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