括号生成问题(leetcode 22)
思路:
- 确定使用递归
- 确定递归剪枝条件:
- 当左括号left大于n时,非法,剪枝
- 当右括号right比左括号left多时,非法,剪枝
- 对于获得排列组合题,构建集合,递归函数带上路径path
- 路径就加个左括号,left就++,加个右括号right就++
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = set()
self.dfs(n, 0, 0, "", res)
return list(res)
def dfs(self, n, left, right, path, res):
if left > n or right > left:
return
if len(path) == n * 2:
res.add(path)
return
self.dfs(n, left+1, right, path+"(", res)
self.dfs(n, left, right+1, path+")", res)
最长有效括号(leetcode 32)
妈呀,这是我在面试华为的时候,出的一道题。
当时用栈做出来了,现在试试DP,逆天的DP,脑子不够用了
DP思路:
- 先对s进行基本的修正,左边为
)
的不可能匹配成功,右边为(
不能匹配成功,直接strip掉 - 边界条件返回0
- 构建dp,dp[0]肯定为0,从1开始遍历
- 判断s[i]为
(
的情况,匹配失败dp[i] = 0 - 判断s[i]为
)
的情况:- 如果 i >= 1 并且 s[i-1] == "(",匹配成功,如果 i == 1, dp[i-2] -> dp[-1] == 0
i == 0 or s[i-1] == ")"
的情况,i==0时,dp[0]=0,不管; 剩下s[i-1] == ")"
的情况,注意i - dp[i-1] > 0
即确定与s[i]对应的"("存在,且为"(",即可得出dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
举个栗子🌰:"()(())",i指向5时,dp[i-dp[i-1]-2] -> dp[5-2-2] == dp[1] == 2
,"(())",i指向3时,dp[i-dp[i-1]-2] -> dp[-1] == 0
PS: dp[i-dp[i-1]-2]
在这种情况下,可能存在也可能不存在,不存在则为 dp[-1] = 0,没有赋值就是0,存在就直接加
class Solution:
def longestValidParentheses(self, s: str) -> int:
s = s.lstrip(")").rstrip("(")
if len(s) == 0:
return 0
dp = [0 for _ in range(len(s))]
for i in range(1, len(s)):
# if s[i] == '(': dp[i] = 0 # 以(结尾非法,dp初始化就为0,可以省略
if s[i] == ')': # 如果为右括号,左边匹配成功且i>=2,dp依赖
if i >= 1 and s[i-1] == '(':
dp[i] = dp[i-2] + 2
else: # 如果匹配不成功,i - dp[i-1]为s[i]的左括号位置(如果有的话)
if i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
return max(dp)
再次强调:第二题DP仅用于锻炼DP能力,本题最优解还是用栈比较好