Concise python code using defaultdict


  • 2
    H

    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[0]: return None
            wl = len(L[0])
            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

  • 0
    D

    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)


  • 2
    Z

    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[0])
        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)


Log in to reply
 

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