99ms Python O(kmn) Solution

  • 10

    The idea comes from [https://leetcode.com/discuss/20151/an-o-n-solution-with-detailed-explanation]

    Using a counter and a sliding window, we push the window from left to right, counting the number of valid words in the window. When the number of a word in the window is more than the times it appears in words or we meet a invalid word, push the window.

    class Solution:
    # @param {string} s
    # @param {string[]} words
    # @return {integer[]}
    def findSubstring(self, s, words):
    	if len(words) == 0:
    		return []
    	# initialize d, l, ans
    	l = len(words[0])
    	d = {}
    	for w in words:
    		if w in d:
    			d[w] += 1
    			d[w] = 1
    	i = 0
    	ans = []
    	# sliding window(s)
    	for k in range(l):
    		left = k
    		subd = {}
    		count = 0
    		for j in xrange(k, len(s)-l+1, l):
    			tword = s[j:j+l]
    			# valid word
    			if tword in d:
    				if tword in subd:
    					subd[tword] += 1
    					subd[tword] = 1
    				count += 1
    				while subd[tword] > d[tword]:
    					subd[s[left:left+l]] -= 1
    					left += l
    					count -= 1
    				if count == len(words):
    			# not valid
    				left = j + l
    				subd = {}
    				count = 0
    	return ans

    Assuming we have k words in words, and there are m substrings in the string, the complexity is O(kmn) because we need to adjust the window when more valid words are found.

    This solution runs 99ms on OJ.

  • 0

    There is a built-in Python Counter that provides this functionality:


    Thanks for the solution!

  • 0

    for k in range(l): can be xrange
    count can be derived from left and j
    code can be simplified a bit by using defaultdict
    the condition of the while loop can be just comparing the strings (between the head to the current at j), should be a bit cheaper than check the count.

  • 7

    I felt that above post could have a little more explanation. I had some difficulty understanding the above solution so I am adding this. It is based on the above approach only but has little detailed comments and uses Counter and defaultdict for ease.

            from collections import Counter
            from collections import defaultdict
            c = Counter(words)
            m = len(words)
            n = len(words[0])
            ret = []
            total_length = m * n            
            #Loop over word length
            for k in xrange(n):
                left = k
                subd = defaultdict(int)
                count = 0
                #Loop over the string
                for j in xrange(k, len(s) - n + 1, n):
                    #Get a word from observed substring
                    word = s[j:j+n]
                    #check if it is a valid word
                    if word in c:
                        subd[word] += 1
                        count += 1
                        ##Shift the window as long as we have encountered more number of a word than is needed
                        ##Note that we can shift the window by word length directly as the outer loop is there to
                        ##make sure that anything is not missed out
                        ##This solution will give indices out of order by OJ accepts it.
                        while subd[word] > c[word]:
                            subd[s[left:left+n]] -= 1
                            left += n
                            count -= 1
                        ##Count will be equal to m only when we all the words are read the exact number of times needed
                        if count == m:
                    #If is not a valid word then just skip over the current word (Don't worry about the middle characters 
                    ##outer loop will take care of it)
                        left = j + n
                        subd = defaultdict(int)
                        count = 0
            return ret

  • 0

    @Anavil Why not just use counter instead of defaultdict?

  • 0

    very nice code.
    I think your code is better than shichaotan's

Log in to reply

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