After solved 1000 medium leetcode found these patterns — Sliding Window, 2 Pointer, String

Sliding Window

start, end = 0, 0
res=0
while end < length(arr or string):
do_something(end)
while decreasing_window_size(start):
dosomething(start)
start +=1
res = max(res, end-start+1) # or min
end+=1
return res
def lengthOfLongestSubstring(self, s: str) -> int:
start, end = 0, 0
arr = defaultdict(int)
res=0
while end < len(s):
arr[s[end]]+=1
while start < end and arr.get(s[end], 0) > 1:
arr[s[start]]-=1
start +=1
res = max(res, end-start+1)
end+=1
return res
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
start, end=0, 0
res=float('inf')
s=0
while end < len(nums):
s += nums[end]
while s>= target+nums[start]:
s -= nums[start]
start += 1
if s >= target:
res = min(res, end-start+1)
end += 1
return 0 if res == float('inf') else res

2 Pointer

Problem 1
xxxxxyyyyyzzzzzzzzzz
| |
left-> <- right
Problem2
ssstrrrrrinng1
|
pointer1->
ssttrrringggg2
|
pointer2->
Problem3
sssssstttrrrrring
| |
slow |
fast
def maxArea(self, height: List[int]) -> int:
"""
maintein left and right index
when height[left] > height[right]: right-1. else left + 1
"""
l,r = 0, len(height)-1
res =0
while l<r:
res = max(res, min(height[l], height[r]) * (r-l))
if height[l]> height[r] :
r -= 1
else:
l += 1
return res
def threeSumClosest(self, nums: List[int], target: int) -> int:
"""
Explaination :
<-sorted(array)->
|--|------------|
left mid right
3 sum = left+mid+right
when 3sum > target:
right-1 (left+1 or mid+1 will make it even bigger)
else :will try mid+1 (left+1 case is covered in outside loop)
"""
nums = sorted(nums)
l,m,r = 0, 1, len(nums)-1
res = nums[l]+nums[m]+nums[r]
while l < len(nums)-1:
m = l+1
r = len(nums)-1
t = nums[l]+nums[m]+nums[r]

while m < r:
three_sum = nums[l]+ nums[m] +nums[r]
if abs(three_sum-target) < abs(res-target):
res = three_sum
if three_sum > target:
r -= 1
else:
m += 1
l += 1
return res
1. when ']' parse previous string
def decodeString(self, s: str) -> str:
i = 0
while i<len(s):
if s[i] == ']':
j = i
while s[j] != '[':
j-=1
s1 = s[j+1:i]
times = ''
k=j-1
while k>=0 and s[k].isdigit():
times=f'{s[k]}{times}'
k-=1
s2=int(times)*s1
s=s[:k+1]+s2+s[i+1:]
i=len(s2)+k
i+=1
return s
2. Use regex search (much cleaner)
def decodeString(self, s: str) -> str:
pattern = '(\d+)\[([a-z]+)\]'
while True:
res = re.search(pattern, s)
if not res:
return s
times, s1 = int(res[1]), res[2]
s = s.replace(f'{times}[{s1}]', times*s1)
return s
3. Use regex sub ( bit slower, but clearer)
def decodeString(self, s: str) -> str:
pattern = '(\d+)\[([a-z]+)\]'
while '[' in s:
s = re.sub(pattern, lambda m: int(m.group(1))*m.group(2), s)
return s

Conclusion

--

--

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