1221. 分割平衡字符串
- 思路
- example
- 贪心或者滑窗
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def balancedStringSplit(self, s: str) -> int:
n = len(s)
cntL, cntR = 0, 0
res = 0
for i in range(n):
ch = s[i]
if ch == 'L':
cntL += 1
else: # ch == 'R'
cntR += 1
if cntL == cntR:
res += 1
cntL, cntR = 0, 0
return res
class Solution:
def balancedStringSplit(self, s: str) -> int:
n = len(s)
L, R = 0, 0
res = 0
for i in range(n):
ch = s[i]
if ch == 'L':
L += 1
else:
R += 1
if L == R:
res += 1
L, R = 0, 0
return res
5. 最长回文子串
- 思路
- example
- 区间DP
dp[i][j]: s[i,...,j]是否回文串
- 复杂度. 时间：
, 空间:
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
res = ''
max_ = 0
for i in range(n-1, -1, -1):
for j in range(i, n): # j >= i
if i == j:
dp[i][j] = True
else: # j > i
if s[i] != s[j]:
dp[i][j] = False
else: # s[i] == s[j]
if j == i + 1:
dp[i][j] = True
else: # j > i + 1
dp[i][j] = dp[i+1][j-1]
if dp[i][j] == True:
if j - i + 1 > max_:
max_ = j - i + 1
res = s[i:j+1]
return res
class Solution:
def longestPalindrome(self, s: str) -> str:
# DP, 2D, dp[i][j]: s[i], ..., s[j]
n = len(s)
dp = [[False for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n-1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
if j - i <= 1:
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = False
if dp[i][j] == True:
if j-i+1 > cnt:
cnt = j-i+1
res = s[i:j+1]
return res
- 双指针，中心扩散法，空间O(1)
- 中心：(i,i)或(i,i+1)
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(s, left, right):
if left > right:
return 0
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left+1, right-1 # closed interval
n = len(s)
max_ = 0
start, end = -1, -1
for i in range(n):
left, right = expand(s, i, i)
length = right - left + 1
if length > max_:
start, end = left, right
max_ = length
left, right = expand(s, i, i+1)
length = right - left + 1
if length > max_:
start, end = left, right
max_ = length
return s[start:end+1]
class Solution:
def longestPalindrome(self, s: str) -> str:
# 中心扩散法 <- ->, time: O(n^2), space: O(1)
def expand(center1, center2):
left, right = center1, center2
while left >= 0 and right < n:
if s[left] == s[right]:
left -= 1
right += 1
else:
break
return left+1, right-1
n = len(s)
res = ''
cnt = 0
for i in range(n):
left, right = expand(i, i)
length = right - left + 1
if length > cnt:
cnt = length
res = s[left:right+1]
left, right = expand(i, i+1)
length = right - left + 1
if length > cnt:
cnt = length
res = s[left:right+1]
return res
