题目:
最长的有效括号
解法1:通过使用栈来实现。遍历字符串,如果字符等于 "(",将该字符的索引放入栈中。如果字符等于")",首先判断栈是否为空,若为空,直接将其索引放入栈中。如果栈不为空,那查看栈顶元素是否为 "(",如果是,进行pop()操作,当前长度等于 当前 “)” 的索引减去pop()操作后的栈顶元素(如果pop()后栈为空,那么当前长度等于索引+1)。
特别注意:栈是否为空
参考代码如下:
class Solution:
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0 or len(s) == 1:
return 0
stack = []
j = 0
max_len = 0
while j < len(s):
if s[j] == "(":
stack.append(j)
if s[j] == ")":
if len(stack) and s[stack[-1]] == "(":
stack.pop()
if len(stack):
lens = j - stack[-1]
if lens > max_len:
max_len = lens
else:
lens = j + 1
if lens > max_len:
max_len = lens
else:
stack.append(j)
j += 1
return max_len
解法2:动态规划(待更新)
动态规划的思路是,我们用一个list:dp 来记录字符串s中第i个元素的有效匹配长度。
当前字符为“)”时,才有可能出现匹配,所以我们关注两种情况:“()”和“))”
- “()”:
dp[i] = dp[i - 2] + 2 #直接在历史匹配数上增加2
2.“))”:
if i - dp[i-1] - 1 >= 0: # 确保没有超出索引
if s[i - dp[i - 1] - 1] == "(": #最后一个“)”是否有匹配
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 # 在历史匹配上增加2
完整代码如下:
class Solution:
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
dp = []
lens = len(s)
if lens < 2:
return 0
# initialize dp lisSt
j = 0
while j < lens:
dp.append(0)
j += 1
i = 1
while i < lens:
if s[i] == ")" and s[i - 1] == "(":
dp[i] = dp[i - 2] + 2
if s[i] == s[i - 1] == ")":
if i - dp[i-1] - 1 >= 0:
if s[i - dp[i - 1] - 1] == "(":
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
i += 1
return max(dp)
源码地址:
https://github.com/jediL/LeetCodeByPython
其它题目:[leetcode题目答案讲解汇总(Python版 持续更新)]
(https://www.jianshu.com/p/60b5241ca28e)
ps:如果您有好的建议,欢迎交流 :-D,
也欢迎访问我的个人博客 苔原带 (www.tundrazone.com)
网友评论