Concise python code using defaultdict

  • 2

    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

    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

    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]
                while temp[word] < 0:
                if j+k-start==n*k:
        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.