LeetCode has a hard coding Problem in Its’ Algorithm Section “Substring with Concatenation of All Words”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE
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.
Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
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.
Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
1 <= s.length <= 104
sconsists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]consists of lower-case English letters.
Solution to Substring with Concatenation of All Words
So, for this question, my current proposal is to cut a substring of the corresponding length (the sum of the lengths of each element in words) from s and then trim this substring according to the length of a single word in words. A list is formed by smaller substrings. To determine if the sorted results of words and lists are the same, compare them. If that’s the case, we’ll go back to the beginning. Otherwise, keep going.
def findSubstring(self, s, words):
:type s: str
:type words: List[str]
dict = collections.defaultdict(int)
for w in words:
dict[w] += 1
l, res = len(words), 
for i in xrange(l):
dict1 = dict.copy()
j = i
while j < len(s) – l + 1:
dict1[s[j : j + l]] -= 1
while dict1[s[j : j + l]] < 0:
dict1[s[i : i + l]] += 1
i += l
j += l
if (j – i) / l == len(words):
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE