87% Python O(n) solution with 2 pointers Sliding window


  • 0
    K

    use 2 pointers sliding window

    class Solution(object):
        def findSubstring(self, s, words):
            """
            :type s: str
            :type words: List[str]
            :rtype: List[int]
            """
            
            word_length = len(words[0])
            td = {}
            rt = []
            for w in words:
                td[w] = 1 if w not in td else td[w] + 1
            for i in xrange(word_length):
                curr_td = {}
                begin = i
                end = i
                count = len(words)
                while end <= (len(s) - word_length):
                    temp = s[end:end+word_length]
                    if temp in td:
                        curr_td[temp] = 1 if temp not in curr_td else curr_td[temp] + 1
                        if curr_td[temp] <= td[temp]:
                            count -= 1
                    end += word_length
                    while count == 0:
                        temp = s[begin:begin+word_length]
                        if temp in td:
                            curr_td[temp] = 1 if temp not in curr_td else curr_td[temp] - 1
                            if curr_td[temp] < td[temp]:
                                count += 1
                        if (end - begin) == len(words) * word_length:
                            rt.append(begin)
                        begin += word_length
    
            return rt
    

Log in to reply
 

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