Python Using the pre-stored dictionary result to calculate the new dictionary


  • 0

    The basic idea of this algorithm is using the pre-processed window[i: j] to update the new window[ i + len(words[0]) : j + len(words[0]) ] in only O(1) time complexity.

    class Solution(object):
        def findSubstring(self, s, words):
            """
            :type s: str
            :type words: List[str]
            :rtype: List[int]
            """
            wordcnt, windowlen, ans = {}, 0, []
            for word in words:
                windowlen += len(word)
                if word not in wordcnt:
                    wordcnt[word] = 1
                else:
                    wordcnt[word] += 1
            diclist = []
            for i in xrange(len(words[0])):
                wincnt = {}
                for j in xrange(i, i + windowlen, len(words[0])):
                    tmpword = s[j: j + len(words[0])]
                    if tmpword not in wincnt:
                        wincnt[tmpword] = 1
                    else:
                        wincnt[tmpword] += 1
                diclist.append(wincnt)
            if windowlen > len(s):
                return ans
            for i in xrange(len(s)):
                window = s[i: i + windowlen]
                wincnt = {}
                wincnt = diclist[ i % len(words[0]) ]
                flag = True
                if i >= len(words[0]):
                    preword = s[i - len(words[0]): i]
                    wincnt[preword] -= 1
                    if wincnt[preword] == 0:
                        del wincnt[preword]
                    postword = s[i + windowlen - len(words[0]): i + windowlen]
                    if postword not in wincnt:
                        wincnt[postword] = 1
                    else:
                        wincnt[postword] += 1
                    diclist[i % len(words[0]) ] = wincnt
                for word in wordcnt:
                    if word not in wincnt or wincnt[word] != wordcnt[word]:
                        flag = False
                        break
                if flag:
                    ans.append(i)
            return ans
    

Log in to reply
 

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