首页 > itarticle > 算法设计与分析

算法设计与分析

admin 1月 11, 2021 0

题目描述

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 ).

Example 1:

Input: “()())()”
Output: [“()()()”, “(())()”]

Example 2:

Input: “(a)())()”
Output: [“(a)()()”, “(a())()”]

Example 3:

Input: “)(“
Output: [“”]

解题思路

本题要在一个不合法的字符串中，去除最少的左右括号使字符串变得合法。
将给定字符串及其子字符串作为一个状态进行BFS，逐渐通过去掉括号的方式进行状态转移，为了避免所有括号都去掉一遍，我对去括号的方式做了一点改进，如果左括号多则只去左括号，如果右括号多则只去右括号。当发现合法的字符串时，将found置为true，使得不会再有字符串添加进队列，保证了去除最少的括号这一条件。

源代码

class  {
public:
    vector<string> removeInvalidParentheses(string s) {
        set<string> visited;
        vector<string> res;
        queue<string> q;
        q.push(s);
        visited.insert(s);
        bool found = false;
        while(!q.empty()) {
            string str = q.front();
            q.pop();
            int valid = isValid(str);
            if(valid == 0) {
                res.push_back(str);
                found = true;
                continue;
            }
            if(found) continue;
            for(int i = 0; i < str.length(); i++) {
                if(str[i] != '(' && str[i] != ')') continue;
                if((str[i] == '(' && valid > 0) || (str[i] == ')' && valid < 0)) {
                    string temp = str.substr(0, i) + str.substr(i + 1);
                    if(visited.count(temp) == 0) {
                        visited.insert(temp);
                        q.push(temp);
                    }
                }
            }
        }
        return res;
    }
    int isValid(string s) {
        int count = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(') count++;
            else if(s[i] == ')') count--;
            if(count < 0) return -1;
        }
        if(count > 0) return 1;
        else if(count == 0) return 0;
    }
};