程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode] Remove Invalid Parentheses

[LeetCode] Remove Invalid Parentheses

編輯:關於C++

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())()”]
“)(” -> [“”]

解題思路

括號總是成對出現的,因此我們只需要記錄尚未匹配的
每次循環時有如下三種情況:

(, 保留或者不保留。 ), 如果我們有未匹配的,則有兩種選擇;否則,只能不保留。 保留其他字符。

因為我們要移除數量最少的括號,我們應該得到最大的匹配()數量,注意下面兩行的順序。

dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);

它可以保證最長的結果出現在比它較短的結果前面。

實現代碼

Java:

// Runtime: 216 ms
public class Solution {
    private List res = new ArrayList();
    private int max = 0;
    public List removeInvalidParentheses(String s) {
        dfs(s, , 0, 0);
        if (res.size() == 0) {
            res.add();
        }

        return res;
    }

    private void dfs(String str, String subRes, int countLeft, int maxLeft) {
        if (str.length() == 0) {
            if (countLeft == 0 && subRes.length() != 0) {
                if (maxLeft > max) {
                    max = maxLeft;
                }
                if (max == maxLeft && !res.contains(subRes)) {
                    res.add(subRes.toString());
                }
            }
            return;
        }

        if (str.charAt(0) == '(') {
            dfs(str.substring(1), subRes.concat((), countLeft + 1, maxLeft + 1);
            dfs(str.substring(1), subRes, countLeft, maxLeft);
        } else if (str.charAt(0) == ')') {
            if (countLeft > 0) {
                dfs(str.substring(1), subRes.concat()), countLeft - 1, maxLeft);
            }
            dfs(str.substring(1), subRes, countLeft, maxLeft);
        } else {
            dfs(str.substring(1), subRes.concat(String.valueOf(str.charAt(0))), countLeft, maxLeft);
        }
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved