Documenting LeetCode solving.
Q1
Hard. Sliding window
Use to hashmaps to count frequency. Use have and need variables to check if there are enough characters in the window.
class Solution:
def minWindow(self, s: str, t: str) -> str:
if t == "": return ""
# Initial countT hashmap to count the frequency of
# each character in string t
countT, window = {}, {}
for c in t:
countT[c] = countT.get(c, 0) + 1
have, need = 0, len(countT)
resLen = float("infinity")
res = [-1, -1]
l = 0
for r in range(len(s)):
c = s[r]
window[c] = window.get(c , 0) + 1
# Update have
if c in countT and window[c] == countT[c]:
have += 1
# Use a loop to pop left most character
while have == need:
# Update result
if (r - l + 1) < resLen:
resLen = r - l + 1
res = [l, r]
# Pop left most character
window[s[l]] -= 1
if s[l] in countT and window[s[l]] < countT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l : r + 1] if resLen != float("infinity") else ""
Q2
Hard. Sliding Window
Use a descending queue to track the largest number in the current window.
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
output = []
# Descending queue
q = collections.deque()
l = r = 0
while r < len(nums):
# Make sure the queue is in descending order
# Pop the item if incoming one is larger
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
# If the left itme in the queue is no longer in the window,
# pop it
if l > q[0]:
q.popleft()
if (r + 1) >= k:
# The largest number in the current window is always
# at the most left position
output.append(nums[q[0]])
# Update l pointer when the first k numbers
# are in the window
l += 1
r += 1
return output
Q3
Easy. Stack
class Solution:
def isValid(self, s: str) -> bool:
stack = []
map = {")": "(", "}": "{", "]": "["}
for c in s:
# If it's a closing character
if c in map:
if stack and stack[-1] == map[c]:
stack.pop()
else:
return False
else:
stack.append(c)
return True if not stack else False