解析
5. Longest Palindromic Substring
# solution 1 - burte force: n * n^2
# - Get every possible substring (O(n^2)), and check whether it is a palindrome (O(n))
# solution 2 - sliding window
# - time: O(n^2)
def longestPalindrome(self, s: str) -> str:
max_len = 0
res = ""
for idx in range(len(s)):
# odd: cbc
l, r = idx, idx
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
cur_len = r - l - 1
if cur_len > max_len:
res = s[l + 1:r]
max_len = cur_len
# even cbbc
l, r = idx, idx + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
cur_len = r - l - 1
if cur_len > max_len:
res = s[l + 1:r]
max_len = cur_len
return res
ref
125. Valid Palindrome
# solution 1 - 左右指针
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
i, j = 0, len(s) - 1
while i < j:
left = s[i]
right = s[j]
if not left.isalnum():
i += 1
continue
if not right.isalnum():
j -= 1
continue
if left.lower() != right.lower():
return False
i += 1
j -= 1
return True
131. Palindrome Partitioning
# backtracking
409. Longest Palindrome
- 之前没有考虑过奇数，则把当前奇数加到res里
- 之前考虑过奇数，
- 当前是偶数，则直接把当前偶数加到res里
- 当前是奇数，则把当前奇数-1，然后加到res里
def longestPalindrome(self, s: str) -> int:
m = {}
for char in s:
if char in m:
m[char] = m[char] + 1
else:
m[char] = 1
res = 0
for v in m.values():
if res & 1 == 1 and v & 1 == 1:
v -= 1
res += v
return res
424. Longest Repeating Character Replacement
def characterReplacement(self, s, k):
max_repeating_len = 0
l = 0
m = {} # space: o(n)
for r in range(len(s)): # time: O(n)
m[s[r]] = m.get(s[r], 0) + 1
while l < r:
total_len = 0
max_len = 0
for char, v in m.items(): # time: O(26)
total_len += v
if v > max_len:
max_len = v
if total_len - max_len <= k:
max_repeating_len = max(max_repeating_len, total_len)
break
else:
m[s[l]] = m[s[l]] - 1
l += 1
return max_repeating_len
ref