[LeetCode][python3]0030. Substring with Concatenation of All Words

  1. My Solution
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:

if not words:
return []
elif words[0]=="":
return list(range(len(s)+1))
elif len(s)<len(words[0]):
return []
self.res=[]
self.wordlen=len(words[0])
self.words=words

def dp(s,start,wordleft,end,key):
if not wordleft:
self.res.append(key)
return
if start>end:
return
target=s[start:start+self.wordlen]
if target in wordleft:
tmp=list(wordleft)
tmp.remove(target)
dp(s,start+self.wordlen,tmp,end,key)
last_start=len(s)-self.wordlen*len(words)
for i in range(last_start+1):
dp(s,i,words,len(s)-self.wordlen+1,i)
return self.res
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words or not words[0]:
return []
n = len(s)
wn, wm = len(words), len(words[0])
t = wn * wm
count = collections.Counter(words)

res = []

for i in range(min(wm, n - t + 1)):
l = r = i
cur = collections.defaultdict(int)
while r + wm <= n:
w = s[r:r+wm]
r += wm
if w not in count:
l = r
cur.clear()
else:
cur[w] += 1
while cur[w] > count[w]:
cur[s[l:l+wm]] -= 1
l += wm
if r - l == t:
res.append(l)

return res

--

--

--

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
N2I

N2I

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

More from Medium

Alcohol Treatment.

The Eat, Pray Love journey

Perspective….