算法题1LVPS

且看一道 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 算法

1.png

时间复杂度 $O(N^3)$

2.png

3.png

时间复杂度 $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 感觉就像说废话一样，所以大家有空可以敲一敲

4.png

这是第一篇 leetcode专题的文章，以后会出更多的~主要还是想一边自己学习的同时和大家一起分享，一起进步，大家可能坐地铁或者什么的也不方便拿出电脑啊啥的，你只要打开文章以及纸笔就算是分析了一道题，也算是节约了时间了~

我当然比不过很多大牛，不过还是希望我包括大家都走在成为大牛的路上...

欢迎关注 不会吃狗的猫不是兔子

感谢大家敬请期待ヾ(≧▽≦*)o