且看一道 LeetCode Hard 赛题
寻找最长合法括号子串
给定包含 '(' 和 ')'的一个字符串, 找到一个最长的合法的括号子串。
Example 1:
Input: "(()"
Output: 2
解释: 最长有效括号子串是 "()"
Example 2:
Input: ")()())"
Output: 4
解释: 最长有效括号子串是 "()()"
这道题是考括号匹配算法，首先第一个想到的肯定是：暴力循环求解咯~
这里补充一下括号匹配算法：一般用 stack 解决，简单来说就是遇到 '(' 就push ‘)’就pop，如果pop失败或者最后stack非空就 return false.否则 return true.
显然匹配判断一下就是 O(N) 复杂度了
题解
首先，先上最简单的 Brute Force 算法
最简单暴力求解
时间复杂度 O(N^3)
动态规划
时间复杂度 O(N)
再来一种贼巧妙的，至少我觉得是，给大家来拓宽一下思路~
别走，小心下一次面试说不定就碰到啦！
栈算法
使得当前最大长度 MaxLength 记录的始终是最长的合法的串
初始 stack.push(-1)
(1) 如果 s[i]='(' ，则 stack.push(i)
(2) 如果 s[i]=')'， 则stack.pop()
若 stack.empty()
stack.push(i)
保证从 '(' 的前一个开始计
若 !stack.empty()
MaxLength=max\{MaxLength,i-stack.top()\}
保证 i-stack.top() 是合法串的长度
没有 code 感觉就像说废话一样，所以大家有空可以敲一敲
这是第一篇 leetcode专题的文章，以后会出更多的~主要还是想一边自己学习的同时 和大家一起分享，一起进步，大家可能坐地铁或者什么的也不方便拿出电脑啊啥的，你只要打开文章以及纸笔就算是分析了一道题，也算是节约了时间了~
我当然比不过很多大牛，不过还是希望我包括大家都走在成为大牛的路上...
欢迎关注 不会吃狗的猫不是兔子
感谢大家敬请期待ヾ(≧▽≦*)o
