Substring with Concatenation of All Words

Question

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

Tags

• String
• Hash Table

Thought

Use two hash tables to solve this problem. One hash table is used to store the information of the words list and the other hash table is used to record the information of the current window in the string s during the loop.

Code

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        n = len(words)
        l = len(words[0])
        res = []
        wordCnt = {}
        for word in words:
            wordCnt[word] = wordCnt[word] + 1 if word in wordCnt else 1
        for i in xrange(len(s) - n * l + 1):
            cnt = 0
            tmpCnt = {}
            while cnt < n:
                word = s[i + l * cnt : i + l * (cnt + 1)]
                if word not in wordCnt:
                    break
                elif word in tmpCnt:
                    if tmpCnt[word] >= wordCnt[word]:
                        break
                    else:
                        tmpCnt[word] += 1
                else:
                    tmpCnt[word] = 1
                cnt += 1
            if cnt == n:
                res.append(i)
        return res