原始题目
- 32. Longest Valid Parentheseshttps://leetcode.com/problems/longest-valid-parentheses/
- Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
- Example 1:
- Input: "(()"
- Output: 2
- Explanation: The longest valid parentheses substring is "()"
- Example 2:
- Input: ")()())"
- Output: 4
- Explanation: The longest valid parentheses substring is "()()"
题目解读
一个字符串全部都是由左右小括号组成, 找出最长的合法 (格式良好) 括号子字符串的长度.
示例 1:((), 结果:((), 长度是 2.
示例 2:)()()), 结果:)()()), 长度是 4.
要点分析
1, 合法的括号是(), 而且它也是最简单.
2, 若干个合法的括号紧挨在一起也是合法的, 如:()()().
3, 若干个合法的括号合理嵌套在一起也是合法的, 如:((())).
4, 把紧挨和嵌套合理组合起来也是合法的, 如:(()()).
注: 3 和 4 这两种情况原始题目中并没有指出.
核心问题
仔细观察思考后, 发现:
1, 就像消消乐一样, 一个左括号和一个右括号一见面就可以消除. 但每次只能消除一对.
2, 整个过程肯定会有多次消除, 如何处理上次消除和本次消除之间的关系是关键, 又有三种情况.
a, 上次消除和本次消除是非常确定的可以合并的, 如:()()..., 不管后面如何, 这两对连续的括号一定可以合并.
b, 上次消除和本次消除是非常确定的不可以合并的, 如:())()..., 不管后面如何, 这两对括号一定不可以合并, 因为被中间这个注定单身的右括号隔开了.
c, 上次消除和本次消除是不确定是否可以合并的, 如:()(()..., 这两对括号暂时还不知道是否最终可以合并, 因为中间这个左括号可能会和后面的消除掉, 也可能不会.
说白了就是一切都是不确定的, 走着变着, 只有走到头, 才会有最终结果.
必须把所有的连续子字符串都找出来, 才知道谁是最长的.
这里的关键点就是如何描述 "连续" 这个问题, 我们采用合并的方式来表达 "连续", 因为连续的就等于可以逐步的全部消除, 所以最后肯定可以全部合并.
实现思路 1, 消除第一对括号, 并记录下来这对括号的索引.
2, 消除第二对括号, 并记录下来它们的索引, 再尝试去和上一次的索引合并. 如:()(), 索引分别是 0,1 和 2,3, 它们是挨着的, 所以合并为 0,3.
如:())()或()((), 索引分别是 0,1 和 3,4, 它们没挨着, 不能合并, 那就都存起来.
如:(()), 索引分别是 1,2 和 0,3, 它们是合理嵌套, 所以合并为 0,3.3, 继续这样走下去, 直到字符串结束. 能合并的索引都已合并完, 你得到的就是所有子字符串的起止索引.
举个例子:()((()()),
首先消除红色的, 索引是 0,1. 然后消除蓝色的, 索引是 4,5, 发现它们不能合并. 因为没挨着.
接着消除绿色的, 索引是 6,7, 可以和 4,5 合并为 4,7. 因为挨着呢.
接着再消除紫色的, 索引是 3,8, 可以和 4,7 合并为 3,8. 因为嵌套着呢.
所以子串就是 0,1 和 3,8, 显然 3,8 最长, 长度是 6.
另一个逆向思维的解法上面的方式, 我们一直在关注消去的部分, 所以就必须很费劲的去合并每次的消去.
我看到有一个老外的思维正好反过来, 他关注剩余部分. 他保留了所有剩余部分的索引, 那消去的自然也就知道了.
这样的好处就是不用去合并每次的消去, 会轻松很多.
还采用上面的例子:()((()()),
消去红色的, 什么都不记录.
消去蓝色的.
消去绿色的.
消去紫色的.
最后就剩下一个黑色的左括号, 它的索引是 2.
整个字符串的索引是 0,8, 中间被 2 隔断了, 所以消去的子串就是 0,1 和 3,8.
尽管原理差不多, 但关注点不同, 是不是比上面简单了许多啊.
PS: 欢迎大家关注我的公众号 "编程新说", 和我一起刷题.
(完)
编程新说
用独特的视角说技术
来源: https://www.cnblogs.com/lixinjie/p/a-post-for-leetcode-32.html