算法细节系列（15）：Valid Parentheses系列
算法细节系列（15）：Valid Parentheses系列
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1435862
算法细节系列（15）：Valid Parentheses系列
详细代码可以fork下Github上leetcode项目，不定期更新。
题目均摘自leetcode：
- Leetcode 020: Valid Parentheses
- Leetcode 022: Great Parentheses
- Leetcode 241: Different Ways to Add Parentheses
- Leetcode 301: Remove Invalid Parentheses
- Leetcode 032: Longest Valid Parentheses
Leetcode 020: Valid Parentheses
Problem:
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘’ and ‘’, determine if the input string is valid. The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “()” are not.
思路：
括号的合法性总共就两个最基本的关系，合并关系()()，包容关系(())，其他情况都是这两种关系的组合。所以假设() == true，那么由于合并和包容的性质也为true，所以我们可以简单的认为() == "" == true，该问题就被解决了。
代码如下：
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '('){
stack.push(s.charAt(i));
}
else{
char c = !stack.isEmpty() ? stack.peek() : '.';
if (s.charAt(i) == ']' && c == '[') stack.pop();
else if (s.charAt(i) == '}' && c == '{') stack.pop();
else if (s.charAt(i) == ')' && c == '(') stack.pop();
else return false;
}
}
return stack.isEmpty();
}Leetcode 022: Great Parentheses
Problem:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”
朴素的做法，考虑所有可能的情况，从中选择合法的序列。代码如下：
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
helper(n, "", ans);
return ans;
}
private void helper(int len, String tmp, List<String> ans){
if (tmp.length() == 2 * len){
if (isValid(tmp))
ans.add(tmp);
return;
}
tmp += '(';
helper(len, tmp, ans);
//回到递归前状态继续搜索
tmp = tmp.substring(0, tmp.length()-1);
tmp += ')';
helper(len, tmp, ans);
tmp = tmp.substring(0, tmp.length()-1);
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '('){
stack.push(s.charAt(i));
}
else{
char c = !stack.isEmpty() ? stack.peek() : '.';
if (s.charAt(i) == ']' && c == '[') stack.pop();
else if (s.charAt(i) == '}' && c == '{') stack.pop();
else if (s.charAt(i) == ')' && c == '(') stack.pop();
else return false;
}
}
return stack.isEmpty();
}上部分代码还有一个问题，tmp在递归函数外累加的一个坏处就是需要对其状态进行维护，而如果直接传参给递归函数的话，会随着函数的返回直接还原到先前状态，所以如上代码片段：
tmp += '(';
helper(len, tmp, ans);
tmp = tmp.substring(0, tmp.length()-1);
tmp += ')';
helper(len, tmp, ans);
tmp = tmp.substring(0, tmp.length()-1);可以直接优化成：
helper(len, tmp + '(', ans);
helper(len, tmp + ')', ans);代码可优化的地方很明显，没有剪去非合法的分枝，导致了很多没必要的搜索。所以，优化版本加入剪枝条件。
思路：
很简单，在生成过程中，只要有一个约束条件即能让序列合法。
- 让添加的右括号的个数始终不能超过左括号的个数。（合法序列：左括号个数等于右括号个数）
所以，我们只要确保最终状态左括号数和右括号数相等，且在生成过程中始终保持左括号个数大于右括号数（注意：生成中的序列不能让左括号个数和右括号个数相等）。此时考虑终止条件，左括号个数等于题目给定的n即可。
代码如下：
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
backtrack(list, "", 0, 0, n);
return list;
}
public void backtrack(List<String> list, String str, int open, int close, int max){
if(str.length() == max*2){
list.add(str);
return;
}
//终止条件（有限层数的搜索）
if(open < max)
backtrack(list, str+"(", open+1, close, max);
//约束条件（序列合法性）
if(close < open)
backtrack(list, str+")", open, close+1, max);
}Leetcode 241: Different Ways to Add Parentheses
Problem:
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1:
Input: “2-1-1”. ((2-1)-1) = 0 (2-(1-1)) = 2 Output: 0, 2
Example 2:
Input: “2*3-4*5” (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 Output: -34, -14, -10, -10, 10
思路：
都可以由每个符号划分成左右两部分，划分的两部分优先级最高，先进行计算。所以该问题就变成了一个递归问题。代码如下：
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '*' || input.charAt(i) == '-' || input.charAt(i) == '+') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
switch (input.charAt(i)) {
case '*': {
for (int a1 : left) {
for (int a2 : right) {
ans.add(a1 * a2);
}
}
}
break;
case '-': {
for (int a1 : left) {
for (int a2 : right) {
ans.add(a1 - a2);
}
}
}
break;
case '+': {
for (int a1 : left) {
for (int a2 : right) {
ans.add(a1 + a2);
}
}
}
break;
default:
break;
}
}
}
//最基础的情况，由纯数字构成，直接返回即可。
if (ans.size() == 0){
ans.add(Integer.valueOf(input));
}
return ans;
}Leetcode 301: Remove Invalid Parentheses
Problem:
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses ( and ).
Examples:
“()())()” -> “()()()”, “(())()” “(a)())()” -> “(a)()()”, “(a())()” “)(” -> “”
思路：
我们知道一个合法的括号序列，左右括号个数相等。所以想法就是检查第一个出现非法状态的右括号，也就是说右括号的个数大于左括号的个数，那么怎样算合法呢？只要删除之前的任意一个右括号即可。一旦删除任意一个右括号，那么左半部分就合法了，而我们只需要递归去删除右半部分即可。为了完成该操作，需要记录两个指针，第一次非法出现的指针last_i以及删除右括号的位置last_j，避免出现重复的答案。
但如果遇到了类似(((()，这种情况，我们知道，如果检测右括号那是检测不出非法状态的，所以我们可以把字符串逆序，重新使用一遍该算法，然后再把结果逆序回来，非常巧妙。代码如下：
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
remove(s, ans, 0, 0, new char[]{'(',')'});
return ans;
}
// last_i 记录了第一个非法的位置
private void remove(String s, List<String> ans, int last_i, int last_j, char[] par){
for (int stack = 0, i = last_i; i < s.length(); ++i){
if (s.charAt(i) == par[0]) stack++;
if (s.charAt(i) == par[1]) stack--;
if (stack >= 0) continue;
for (int j = last_j; j <= i; ++j){
if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j-1) != par[1])){ //去重
remove(s.substring(0, j) + s.substring(j+1, s.length()), ans, i, j, par);
}
}
return;
}
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '('){
remove(reversed, ans, 0, 0, new char[]{')', '('});
}else{
ans.add(reversed);
}
}Leetcode 032: Longest Valid Parentheses
Problem:
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
朴素的做法：
使用栈，想法很简单，栈记录那些非法括号的下标，那么遍历一遍后，所有的合法括号都相互抵消，剩下的都是些无法抵消的非法位置。而非法位置之间的长度即为我们的候选答案，取所有候选最大即可。代码如下：
public int longestValidParentheses(String s) {
int n = s.length();
Stack<Integer> stack = new Stack<>();
char[] c = s.toCharArray();
for (int i = 0; i < n; i++){
if (c[i] == '('){
stack.push(i);
}else{
if (!stack.isEmpty()){
if (c[stack.peek()] == '(') stack.pop();
else stack.push(i);
}else{
stack.push(i); //推入非法的下标
}
}
}
int max = 0;
if (stack.isEmpty()) max = n;
else{
int curr = n;
int next = 0;
while (!stack.isEmpty()){
next = stack.pop();
max = Math.max(max, curr-next-1);
curr = next;
}
max = Math.max(max, curr);
}
return max;
}上述代码虽然运行时间为O(n)O(n)，但是为了抵消一些合法序列，需要进栈出栈两个操作，且最后还需要遍历一遍非法序列。
优化思路：
前文说了，合法序列有两种基本模式：合并关系和包容关系，如下。
合并关系：
()
包容关系：
(())
所以，对我们来说，只要我们能找到一种算法能够算出这两种关系的答案即可。
我们用dp表示:
dp[i]：表示在下标i的合法序列长度
如：
() dp[1] = 2;
(()) dp[3] = 4;
()) dp[2] = 0;
我们知道合法序列的等价条件：左括号个数等于右括号个数
所以，我们以 ')'为目标，遇到 '('的情况，dp均为0，因为它不可能合法。
两种情况：
a.合并关系的更新：
()
if c[i] == ')' && c[i-1] == '('
dp[i] = 2;
假设前面还存在合法序列，如：
()()
dp[i] = dp[i-2] + 2;
b.包容关系的更新：
(())
if c[i] == ')' && c[i-1] == ')' && c[i-dp[i-1]-1] == '('
dp[i] = dp[i-1] + 2;
假设前面还存在合法序列，如：
()(())
dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
这样，所有情况都考虑到了，我们在设置一个max随时更新最大即可。代码如下：
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n];
char[] c = s.toCharArray();
int max = 0;
for (int i = 0; i < n; i++){
if (c[i] == ')'){
if (i != 0 && c[i-1] == '('){
dp[i] = ((i - 2) != -1 ? dp[i-2] : 0) + 2;
}
if (i != 0 && c[i-1] == ')'){
if (i - dp[i-1] -1 != -1 && c[i-dp[i-1]-1] == '('){
dp[i] = dp[i-1]+2 + (i -dp[i-1]-2 != -1 ? dp[i-dp[i-1]-2] : 0);
}
}
max = Math.max(max, dp[i]);
}
}
return max;
}总结：
- 注意括号的等价条件，左括号个数等于右括号个数。
- 括号相关都可以用stack进行抵消操作。
- 注意最本质的两个元关系，【包容】和【合并】，只要能够设计出有效的算法满足它们即能得到有效解。