# hashmap + sorting - myself
# - time: O(N * max_char log max_char)
# - space: O(n)
def groupAnagrams(self, strs):
m = {}
for str in strs:
sortedStr = "".join(sorted(str))
if sortedStr in m:
m[sortedStr].append(str)
else:
m[sortedStr] = [str]
return m.values()
# hashmap - myself
# - time: O(n * max_char)
# - space: O(n)
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
m = {}
for str in strs: # time: O(n)
curSign = [0] * 26
for char in str: # time: O(max_char)
curSign[ord(char) - ord("a")] += 1 # ord("a") means the ASCII of "a"
# because Python cannot use list as the keys of a list
if tuple(curSign) in m:
m[tuple(curSign)].append(str)
else:
m[tuple(curSign)] = [str]
return m.values()
ref
...A string is palindromic if it reads the same forward and backward.
# burte force
# - time: O(n^3) # n to check a sub-str being a palindrome or not, n^2 to chekc all possible sub-str
# - space: O(1)
# - Get every possible substring (O(n^2)), and check whether it is a palindrome (O(n))
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
res, resLen = "", 0
for i in range(len(s)):
for j in range(i, len(s)):
l, r = i, j
while l < r and s[l] == s[r]:
l += 1
r -= 1
# l >= r 以判断 l 和 r 是否相遇了，如果相遇了，说明 s[i:j+1] 为 palindrome
if l >= r and resLen < (j - i + 1):
res = s[i: j + 1]
resLen = j - i + 1
return res
# 双指针
# - time: O(n^2)
# - space: O(1)
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
maxLen = 0
res = ""
for i in range(len(s)):
# odd length, e.g., cbc in cbc
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
curLen = r - l + 1 # 计算两指针包括的元素长度
if curLen > maxLen:
maxLen = curLen
res = s[l:r + 1]
l -= 1
r += 1
# even length, e.g., bb in cbbc
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
curLen = r - l + 1 # 计算两指针包括的元素长度
if curLen > maxLen:
maxLen = curLen
res = s[l:r + 1]
l -= 1
r += 1
return res
# ??
# Manacher's Algorithm
# - time: O(n)
# - space: O(1)
def longestPalindrome(self, s: str) -> str:
def manacher(s):
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n
l, r = 0, 0
for i in range(n):
p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
and t[i + p[i] + 1] == t[i - p[i] - 1]):
p[i] += 1
if i + p[i] > r:
l, r = i - p[i], i + p[i]
return p
p = manacher(s)
resLen, center_idx = max((v, i) for i, v in enumerate(p))
resIdx = (center_idx - resLen) // 2
return s[resIdx : resIdx + resLen]
ref
...# Approach 1 - more elegent
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
for idx in range(1, len(nums)):
res[idx] = res[idx - 1] * nums[idx - 1]
temp = nums[-1]
for idx in range(len(nums) - 2, -1, -1):
res[idx] = res[idx] * temp
temp = temp * nums[idx]
return res
# Approach 2 - just a bit easier to understand
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
temp = nums[0]
for idx in range(1, len(nums)):
res[idx] = temp
temp = temp * nums[idx]
temp = nums[-1]
for idx in range(len(nums) - 2, -1, -1):
res[idx] = res[idx] * temp
temp = temp * nums[idx]
return res
# brute force
# - time: O(n2)
# - space: O(1)
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# sort + 双指针
# - time: O(nlogn)
# - space: O(n)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
A = [] # 记录排序前，元素 num 的原始索引（因为结果中需要返回原始索引）
for i, num in enumerate(nums):
A.append([num, i])
A.sort() # A 将按照每个二元组的第一个元素（即数值）从小到大排序
i, j = 0, len(nums) - 1 # i 指向数组左端（最小值），j 指向数组右端（最大值）
while i < j:
cur = A[i][0] + A[j][0]
if cur == target:
return [A[i][1], A[j][1]]
elif cur < target:
i += 1
else:
j -= 1
return []
# hashmap
# - time: O(n)
# - space: O(n)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
prevMap = {} # prevMap 中存储的都是可以被考虑的数字
for i in range(len(nums)):
num = nums[i]
diff = target - num
if diff in prevMap:
return [i, prevMap[diff]]
prevMap[num] = i
# brute force
# - time: O(n^2)
# - space: O(1)
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return []
# 左右指针（双指针）
# - time: O(n)
# - space: O(1)
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
l, r = 0, len(numbers) - 1
while l < r:
cur_sum = numbers[l] + numbers[r]
if cur_sum == target:
return [l + 1, r + 1]
elif cur_sum > target:
r -= 1
else:
l += 1
ref
...
min(h[l], h[r]) * (r - l)height[l] 和 height[r]的大小，如果 height[l] 小，l++，因为此时移动 r，并不会改变结果
# brute force
# - time: O(n2)
# - space: O(1)
# 双指针
# - time: O(n)
# - space: O(1)
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
max_water = 0
while l < r:
cur_water = (r - l) * min(height[l], height[r])
max_water = max(max_water, cur_water)
if height[l] < height[r]:
l += 1
else:
r -= 1
return max_water
ref
...