↓Skip to main content
  1. Posts/

LeetCode-301 删除无效的括号

·1 min·
Table of Contents

LeetCode-301 删除无效的括号 #

Solution 1 #

要求返回所有的可能结果, 同时要求删除步数最小, 所以使用深度优先搜索. 具体实现时, 模拟每一步可能的删除情况, 同时用一个 $set$ 去重. 代码如下:

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (auto ch: s) {
            if (ch == '(') {
                st.push(ch);
            }
            else if (ch == ')') {
                if (st.empty()) {
                    return false;
                }
                st.pop();
            }
        }
        return st.empty();
    }

    vector<string> removeInvalidParentheses(string s) {
        set<string> book;
        queue<string> q;
        
        vector<string> ans; 
        book.insert(s);
        q.push(s);
        if (isValid(s)) {
            ans.push_back(s);
            return ans;
        }
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                string t = q.front();
                cout<<t<<endl;
                q.pop();
                book.erase(t);
                for (int i = 0; i < t.size(); i++) {
                    if (t[i] != '(' && t[i] != ')') {
                        continue;
                    }
                    string ns = "";
                    for (int j = 0; j < t.size(); j++) {
                        if (j != i) {
                            ns += t[j];
                        }
                    }
                    if (!book.count(ns)) {
                        book.insert(ns);
                        q.push(ns);
                        if (isValid(ns)) {
                            ans.push_back(ns);
                        }
                    }                    
                }
                
            }
            if (ans.size() != 0) {
                return ans;
            }
        }
        return ans;
    }
};