我的LeetCode代码仓：https://github.com/617076674/LeetCode
 
原题链接：https://leetcode-cn.com/problems/remove-invalid-parentheses/
 
题目描述：
 
 
知识点：回溯
 
思路一：回溯法（用栈来判断括号是否匹配）
 
由于没有任何剪枝操作，该回溯过程穷举了所有可能的情形，时间复杂度是O(2 ^ n)，其中n为括号个数。空间复杂度是O(m)，其中m为字符串的长度。
 
JAVA代码：
 
public class Solution {

    private Set<String> set;

    private String input;

    private int maxLen = 0;

    public List<String> removeInvalidParentheses(String s) {
        set = new HashSet<>();
        input = s;
        removeInvalidParentheses(0, "", new LinkedList<>());
        return new ArrayList<>(set);
    }

    private void removeInvalidParentheses(int index, String valid, LinkedList<Character> linkedList) {
        if (index == input.length()) {
            if (linkedList.isEmpty()) {
                if (maxLen < valid.length()) {
                    maxLen = valid.length();
                    set.clear();
                    set.add(valid);
                } else if (maxLen == valid.length()) {
                    set.add(valid);
                }
            }
            return;
        }
        char c = input.charAt(index);
        if (c == '(') {
            removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
            linkedList.push(c);
            removeInvalidParentheses(index + 1, valid + c, linkedList);
        } else if (c == ')') {
            if (linkedList.isEmpty()) {
                removeInvalidParentheses(index + 1, valid, linkedList);
            } else {
                removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
                linkedList.pop();
                removeInvalidParentheses(index + 1, valid + c, linkedList);
            }
        } else {
            removeInvalidParentheses(index + 1, valid + c, linkedList);
        }
    }

}
 
LeetCode解题报告：
 
 
思路二：回溯法（用左括号的数量和右括号的数量来判断是否是有效字符串）
 
时间复杂度是O(2 ^ n)，其中n为括号个数。空间复杂度是O(m)，其中m为字符串的长度。但少了思路一中的入栈和出栈操作，因此速度上会有所提升。
 
JAVA代码：
 
public class Solution {

    private Set<String> set;

    private String input;

    private int maxLen = 0;

    public List<String> removeInvalidParentheses(String s) {
        set = new HashSet<>();
        input = s;
        removeInvalidParentheses(0, "", 0, 0);
        return new ArrayList<>(set);
    }

    private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) {
        if (leftCount < rightCount) {
            return;
        }
        if (index == input.length()) {
            if (leftCount == rightCount) {
                if (maxLen < valid.length()) {
                    maxLen = valid.length();
                    set.clear();
                    set.add(valid);
                } else if (maxLen == valid.length()) {
                    set.add(valid);
                }
            }
            return;
        }
        char c = input.charAt(index);
        if (c == '(') {
            removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
            removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount);
        } else if (c == ')') {
            removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
            removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1);
        } else {
            removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount);
        }
    }

}
 
LeetCode解题报告：
 
 
思路三：回溯（带剪枝操作）
 
 
如上图所示，Solution1和Solution2的结果可以由很多种回溯过程得到，这些回溯过程对于我们来说其实是多余的，因为得到的是完全相同的结果。对比上图中的6种解决方案，我们发现需要删除的左括号数都是2个，需要删除的右括号数都是0个。事实上，只要题目给出了相应的字符串，我们就能确定需要删除的左括号个数和右括号个数，使得删除的总括号数最少。
 
一旦确定了需要删除的左括号个数和右括号个数，我们的回溯过程就能大大简化。
 
递归出口：
 
在递归遍历完字符串之后，只要满足需要删除的左括号个数和右括号个数均为0，该结果就是满足条件的一个答案。
 
递归过程：
 
（1）如果当前字符是左括号，如果需要删除的左括号个数leftRem大于0，可以考虑忽略该左括号。当然，还有一种情形是不忽略该左括号。
 
（2）如果当前字符是右括号，如果需要删除的右括号个数rightRem大于0，可以考虑忽略该右括号。当然，还有一种情形——当左括号个数leftCount大于右括号个数rightCount时，不忽略该右括号。
 
（3）如果当前字符既不是左括号也不是右括号，直接将该字符加进结果即可。
 
时间复杂度在最坏情况下依然是O(2 ^ n)，其中n为括号的数量。空间复杂度是O(m)，其中m为字符串的长度。
 
JAVA代码：
 
public class Solution {

    private Set<String> set;

    private String input;

    public List<String> removeInvalidParentheses(String s) {
        set = new HashSet<>();
        input = s;
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            } else if (c == ')') {
                if (left == 0) {
                    right++;
                } else {
                    left--;
                }
            }
        }
        removeInvalidParentheses(0, "", 0, 0, left, right);
        return new ArrayList<>(set);
    }

    private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount, int leftRem, int rightRem) {
        if (index == input.length()) {
            if (leftRem == 0 && rightRem == 0) {
                set.add(valid);
            }
            return;
        }
        char c = input.charAt(index);
        if (c == '(') {
            if (leftRem > 0) {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem - 1, rightRem);
            }
            removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount, leftRem, rightRem);
        } else if (c == ')') {
            if (rightRem > 0) {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem, rightRem - 1);
            }
            if (rightCount < leftCount) {
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1, leftRem, rightRem);
            }
        } else {
            removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount, leftRem, rightRem);
        }
    }

}
 
LeetCode解题报告：
 
 
 

题目：http://poj.org/problem?id=1400
 
一开始在判断括号内是否全是乘或除时忘了括号内还有括号的情况，WA了两次之后找到了数据，对比答案之后才发现这个问题……删括号规则：
 
（1）括号前是除号，不能删
 
（2）括号前是乘号或减号，如果括号内全是乘除法或者被括号括起来的运算
 
（3）括号前是加法，如果括号后面是加法、括号后面是减法、括号内全是乘除法或者被括号括起来的运算
 

 
 

#include <string>
#include <iostream>
using namespace std;

inline bool isOperator(char c){
    return c == '+' || c == '-' || c == '*' || c == '/';
}
bool allMulOrDiv(const string& exp)
{
    for(int i = 0, len = exp.size(); i < len; ++i){
        if(exp[i] == '('){
            int cnt = 1;
            for(++i; true; ++i){
                if(exp[i] == '(') ++cnt;
                else if(exp[i] == ')'){
                    --cnt;
                    if(!cnt) break;
                }
            }
            ++i;
        }
        if(exp[i] == '+' || exp[i] == '-') return false;
    }
    return true;
}
int findMatchedLeft(const string& exp, int r)
{
    int countOfRight = 1;
    for(--r; r >= 0; --r){
        if(exp[r] == ')') ++countOfRight;
        else if(exp[r] == '('){
            --countOfRight;
            if(!countOfRight) break;
        }
    }
    return r;
}
string& simplify(string& exp)
{
    int left, right = 0;
    char head, tail, can;
    while((right = exp.find(')', right)) != string::npos){
        left = findMatchedLeft(exp, right);
    //get info
        if(left && isOperator(exp[left-1])) head = exp[left-1];
        else head = '+';
        if(right+1 < exp.size() && isOperator(exp[right+1])) tail = exp[right+1];
        else tail = '+';
    //analyze
        if(right - left == 2) can = 1;
        else if(head == '/') can = 0;
        else if(head == '*' || head == '-') can = allMulOrDiv(exp.substr(left+1, right-left-1));
        else can = tail == '+' || tail == '-' || allMulOrDiv(exp.substr(left+1, right-left-1));
    //process
        if(can){
            exp.erase(left, 1).erase(right - 1, 1);
            --right;
        }
        else ++right;
    }

    return exp;
}

int main()
{
    ios::sync_with_stdio(false);
    int test;
    cin >> test;
    while(cin.get() != '\n') cin.get();
    string exp;
    while(test--){
        getline(cin, exp);
        cout << simplify(exp) << "\n";
    }
    return 0;
}

 

题目描述
 
小A有一个只包含左右括号的字符串S。但他觉得这个字符串不够美观，因为它不是一个合法的括号串。一个合法的括号串是这样定义的： 
 1. ()是合法的括号串 
 2. 若A是合法的括号串，则(A)则是合法的括号串 
 3. 若A，B是合法的括号串，则AB也是合法的括号串。
 
小A现在希望删掉S中若干个字符，使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是不同的，当且仅当他们删除的位置不同。比如当S是(()时，有两种方案。分别是删掉第一个位置，或是删掉第二个位置。
 
输入描述:
 
第一行一个整数n，代表S的长度。 
 第二行输入n个字符，字符要么是(，要么是)。代表串S。
 
输出描述:
 
一行一个整数，代表不同的方案数。答案对10^9+7取模。
 
示例1
 
输入
 
8 
 )(()(())
 
输出
 
30
 
备注:
 
20%: n <= 20 
 40%: n <= 100 
 60%: n <= 1000 
 100%: n <= 10000
 
思路
 
动态规划，但是只需要使用一维的DP 
 dp[j]就意味着还有多少个左括号 也就是‘（’； 
 原因十分的简单，根据题目要求我们就可以知道，左括号需要和右括号匹配，但是只有一个右括号是没有什么用的。 
 打个比方 ： 
 （） 就可以成为一个合法的括号串； 
 ）（ 就不可以成为一个合法的括号串。
 
代码
 
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
char ch[10001];
long long dp[10001];

int main()
{
    int n;
    cin>>n;
    cin>>ch;
    dp[0]=1;
    for(int i=0;i<n;i++)
    {
        if(ch[i]=='(')
        {
            for(int j=n-i;j>=0;j--)
                dp[j+1]=(dp[j+1]+dp[j])%mod;
        }
        else
        {
            for(int j=1;j<=n-i;j++)
                dp[j-1]=(dp[j-1]+dp[j])%mod;
        }
    }
    cout<<((dp[0]-1)+mod)%mod;
    return 0;
}
 
来源：nkw

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
 
说明: 输入可能包含了除 ( 和 ) 以外的字符。
 
示例 1:
 
输入: "()())()"
输出: ["()()()", "(())()"]
 
示例 2:
 
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
 
示例 3:
 
输入: ")("
输出: [""]
 
这道题翻译了discuss的最高票解答（能看懂答案就不错了）
 
这道题的基本思想是找到多余的括号（注意是所有的），所以基本思路是采用回溯法找到所有有效解，然后加入答案中，先来看几点启发：
 
1：怎么找到多余的括号，在Valid Parentheses中，通过stack或者两个计数器left和right分别记录左括号和右括号的个数，可以验证一个左右括号是否符合要求。
 
2：如何限制在指定序列中的有效括号数，比如str=()())，采用计数方法（left和right计数器）来统计，发现left=2，right=3，由于left-right>=0，所以当前的子字符串多了一个右括号，需要删除一个)，我们可以删除str[1]，形成str=(())，也可以删除str[3]，形成str=()()，为了避免重复出现答案，这里规定只删除第一个不符合要求的左括号，因为第二种情况会在后面的回溯中遍历到)。
 
我们规定几个变量的意思：start_to_count开始计数左右括号的位置，start_to_remove开始准备删除第一个不符合要求右括号的起始搜索点（start_to_remove<=start_to_count）
 
class Solution {
public:
    void Core(string s,vector<string> & res,int start_to_count,int start_to_remove,vector<char> &par){
        int count=0; //采用计数器来统计左右括号数
        for(int i=start_to_count;i<s.size();i++){
            if(s[i]==par[0]){
                count++; //遇到左括号就+1
            }
            if(s[i]==par[1]){
                count--; //遇到右括号就-1
            }
            if(count>=0) continue; 如果左括号个数>=右括号个数，继续寻找
            
            for(int j=start_to_remove;j<=i;j++){ //能进到for循环表示count小于0，表示一定要删除一个右括号，那么从start_to_remove开始寻找，找到第一个不满足要求的右括号的位置。
                if(s[j]==par[1] && (j==start_to_remove || s[j-1]!=par[1])){ //第一个多余的右括号的下标是s[j]==par[1]，但是也要考虑边界条件：比如j是第一个元素这种情况
                    Core(s.substr(0,j)+s.substr(j+1),res,i,j,par); //那么删除第一个右括号后的有效字符串就是把第j个字符删掉的剩下的字符串，即new_str=s.substr(0,j)+s.substr(j+1)，由于前面i个（下标）字符已经是有效的字符，且把第j个字符给删了，还要考虑新字符串new_str的长度少了1，那么新的开始搜索的字符下标new_start_to_count=i+1-1=i，同理new_start_to_remove=j+1-1，所以递归调用自身，对应参数设置如上所示。
                }
            }
            return;  //return这里已经处理了剩下子串的所有情况，直接返回，不然会有重复数据。
        }
        reverse(s.begin(),s.end()); //反转原字符，从右往左搜索删除多余的左字符
        if(par[0]=='('){
            vector<char> tmp={')','('};
            Core(s,res,0,0,tmp);
        }
        else res.push_back(s);
    }
    vector<string> removeInvalidParentheses(string s) {
        vector<char> par={'(',')'};
        vector<string> res;
        Core(s,res,0,0,par);
        return res;
    }
};