LC30 - Substring With Concatenation of All Words

Description

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.

Example 1:
Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:
Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []

Example 3:
Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]

Constraints:
1 <= s.length <= 104
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solutions

Solved with a sliding window and two HashMaps.

We store all the words in the HashMap, the key directly stores the word, and the value stores the number of occurrences of the word (because the given word may be repeated, so it may be 1 or 2 or other).
Scan the words of the substring, if the word currently scanned is in the previous HashMap, store the word in the new HashMap
The substring scan ends, if all the words of the substring match, then the substring is one of the ones we are looking for

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        hashWords = {}
        for word in words:
            if word not in hashWords:
                hashWords[word] = 1
            else:
                hashWords[word] +=1
        
        i, j = 0, len(words)*len(words[0])-1
        ans = []
        while j < len(s):
            sub = s[i:j+1]
            temp = {}
            for k in range(0, j-i+1, len(words[0])):
                cur = sub[k:k+len(words[0])]
                if cur not in temp:
                    temp[cur] =1
                else:
                    temp[cur]+=1
                
            if temp == hashWords:
                ans.append(i)
            i+=1
            j+=1
        return ans

use libraray collections.Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        wl, wsl = len(words[0]), len(words)
        i, j = 0, wl*wsl -1
        ans = []
        
        wordsHash = collections.Counter(words)
        
        while j < len(s):
            sub = s[i:j+1]
            subs = []
            for k in range(0, j-i+1, wl):
                subs.append(sub[k:k+wl])
            
            subsHash = collections.Counter(subs)
            if wordsHash == subsHash:
                ans.append(i)
            i+=1
            j+=1
        return ans

Note

>>> from collections import Counter
>>>
>>> myList = [1,1,2,3,4,5,3,2,3,4,2,1,2,3]
>>> print Counter(myList)
Counter({2: 4, 3: 4, 1: 3, 4: 2, 5: 1})
>>>
>>> print Counter(myList).items()
[(1, 3), (2, 4), (3, 4), (4, 2), (5, 1)]
>>>
>>> print Counter(myList).keys()
[1, 2, 3, 4, 5]
>>>
>>> print Counter(myList).values()
[3, 4, 4, 2, 1]

1.30. Substring with Concatenation of All Words ↩