LC 0030 [H] Substring with Concatenation of All Words - ALawliet/algorithms GitHub Wiki
O(m*n*len)
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
freq = Counter(words)
res = []
word_len = len(words[0])
for i in range((len(s) - (len(words) * word_len)) + 1): # char loop
seen = Counter()
for j in range(len(words)): # word loop
next_word_index = i + (j * word_len)
# Get the next word from the string
word = s[next_word_index:next_word_index+word_len]
# Break if the sliced word is not in the dict
if word not in freq: break # not in words
# Add the word to the 'words_seen' map
seen[word] += 1
# No need to process further if the word has higher frequency than exactly once limit
if seen[word] > freq.get(word, 0): break
if j + 1 == len(words): # Store index if we have found all the words
res.append(i)
return res
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
freq = Counter(words)
res = []
word_len = len(words[0])
for i in range((len(s) - (len(words) * word_len)) + 1):
seen = Counter()
for j in range(len(words)):
next_word_index = i + (j * word_len)
word = s[next_word_index:next_word_index+word_len]
if word not in freq: break
seen[word] += 1
if seen[word] > freq.get(word, 0): break
if j + 1 == len(words):
res.append(i)
return res