APP
一、有效的括號
此題在《??數(shù)據(jù)結(jié)構(gòu)與算法——棧與隊列??》中出現(xiàn)
二、括號生成
此題在《??數(shù)據(jù)結(jié)構(gòu)與算法——廣度優(yōu)先與深度優(yōu)先搜索??》中出現(xiàn)
三、最長有效括號
此題為leetcode??第32題??
思路：考慮使用動態(tài)規(guī)劃，定義狀態(tài)dp[i]為以第i個元素結(jié)尾的最長有效括號的長度。有效的括號一定是以“）”結(jié)尾的，因此我們只需考察以“）”的字符，狀態(tài)轉(zhuǎn)移方程如下圖所示。注意dp的邊界條件，圖中并沒有體現(xiàn)出來。
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
res = 0
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(' and i - 2 >= 0:
dp[i] = dp[i - 2] + 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(': # s[i - 1] == ')'
if i - dp[i - 1] - 2 >= 0:
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
else:
dp[i] = dp[i - 1] + 2
res = max(res, dp[i])
return res
四、刪除無效的括號
此題為leetcode??第301題??
思路：可以使用DFS和BFS兩種方式。（1）DFS，首先需要知道要刪除幾個左括號和右括號，分別記為cntleft和cntright，挨個遍歷，除了能配對的，統(tǒng)計剩下的左右括號個數(shù)。然后在原始字符串上面進行刪除操作，遍歷刪除的字符位置[0, len(s)-1], 對應(yīng)字符為左右括號時，分別遞歸；當前刪除位置需要傳遞給下一次遞歸，因為每次刪除一個字符后，字符串長度是減少1的，而刪除的位置正好是下一次迭代中開始刪除的首位。是在循環(huán)刪除的時候，如果下一個字符和上一次回溯結(jié)束后的字符一樣時，不需要再重復(fù)處理。當cntleft和cntright都為0時，檢查字符串s是否有效。（2）BFS，從刪除一個括號開始枚舉，依次刪除2個括號、3個括號等等，分別為level 1、level 2、level 3等等。如果有某一層能有一個及以上的字符串合法，那么所有合法的字符串即為答案，不用在繼續(xù)下去，因為已經(jīng)滿足了“刪除最小數(shù)量的括號”的要求。
# DFS
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# 確定有幾個多余的括號
cntleft, cntright = 0, 0
for c in s:
if c == '(':
cntleft += 1
if cntleft > 0 and c == ')':
cntleft -= 1
elif cntleft == 0 and c == ')':
cntright += 1
self.res = []
self.dfs(s, 0, cntleft, cntright)
return self.res
def is_valid(self, s):
count = 0
for c in s:
if c == '(':
count += 1
if c == ')':
count -= 1
if count < 0:
return False
return count == 0
def dfs(self, s, start, cntleft, cntright):
if cntleft == 0 and cntright == 0 and self.is_valid(s):
self.res.append(s)
for i in range(start, len(s)):
# 如果相鄰的兩個字符相同，那么只刪除一個就行
if i > start and s[i] == s[i - 1]:
continue
if s[i] == '(' and cntleft > 0:
self.dfs(s[:i] + s[i+1:], i, cntleft - 1, cntright)
if s[i] == ')' and cntright > 0:
self.dfs(s[:i] + s[i+1:], i, cntleft, cntright - 1)
# BFS
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# 判斷括號是否合法
def is_valid(s):
count = 0
for c in s:
if c == '(':
count += 1
if c == ')':
count -= 1
if count < 0:
return False
return count == 0
# BFS
level = {s}
while True:
valid_level = list(filter(is_valid, level)) # 將level里合法的字符串篩選出來
if valid_level: # 如果level不為空則找到了結(jié)果
return valid_level
# 挨個進入下一層
next_level = set() # 用set是為了去重
for item in level:
for i in range(len(item)):
if item[i] in '()': # 如果是括號就去掉
next_level.add(item[:i] + item[i + 1:])
level = next_level
本文摘自 ：https://blog.51cto.com/u
