Loading...
墨滴

Persistence

2021/04/03  阅读:39  主题:兰青

LeetCode 301. 删除无效括号

301. 删除无效括号

1. 问题描述

给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回

示例 1:

输入: "()())()"
输出: ["()()()""(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()""(a())()"]
示例 3:

输入: ")("
输出: [""]
 

示例 1:

输入:s = "()())()"
输出:["(())()","()()()"]
示例 2:

输入:s = "(a)())()"
输出:["(a())()","(a)()()"]
示例 3:

输入:s = ")("
输出:[""]

2. 题解

我们拿到题之后先审题,题目是一个求所有可能解的问题,能想到的解决办法就是回溯(DFS)。 DFS的解题套路如下:

void dfs(){
    // 终止条件,将中间结果集加入最终结果集
    // 遍历所有的选择
    // 回退当前的选择
}

将模版套用到该题中,我们写出的dfs函数如下

    // index 当前遍历的下标
    // leftCount 已经遍历的左括号的数量
    // rightCount 已经遍历的右括号的数量
    // leftRemoveCount 最少应该删除的左括号的数量
    // rightRemoveCount 最少应该删除的右括号的数量
    // path 中间结果
    private void dfs(int index, int leftCount, int rightCount, int leftRemoveCount, int rightRemoveCount, StringBuilder path){

        // 终止条件,遍历的下标到达末尾,最少应该删除的左括号数量为0,而且最少应该删除的右括号数量为0
        if (index == len) {
            if (leftRemoveCount == 0 && rightRemoveCount == 0) {
                result.add(path.toString());
            }
            return;
        }
        // 当前字符串
        char currentChar = charArray[index];
        // 可能的操作1 删除当前的字符
        // 当前字符为左括号,index+1,leftRemoveCount(最少应该删除的右括号的数量)-1
        if(currentChar == '(' && leftRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount - 1, rightRemoveCount, path);
        }
        // 当前字符为右括号,index+1,rightRemoveCount(最少应该删除的右括号的数量)-1
        if (currentChar == ')' && rightRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount - 1, path);
        }
        // 可能的操作2将当前字符加入中间结果 
        path.append(currentChar);
        // 若当前字符不为左右括号,index+1
        if (currentChar != '(' && currentChar != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount, path);
        // 当前字符为左括号,index+1,leftCount(已经遍历的左括号数量)+1
        } else if (currentChar == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemoveCount, rightRemoveCount, path);
        // 当前为右括号而且右括号的数量小于左括号,则将右括号加入进来,index+1,rightCount(已经遍历的右括号的数量)+1   
        } else if (currentChar == ')' && rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemoveCount, rightRemoveCount, path);
        }
        // 回退
        path.deleteCharAt(path.length() - 1);
    }

3. 参考代码

完整的参考代码如下

class Solution {
    // 要求不重复,用HashSet存储
    private HashSet<String> result = new HashSet<>();
    // 输入的字符长度
    private int len;
    // 输入字符转化为数组
    private char[] charArray;
    public List<String> removeInvalidParentheses(String s) {

        this.len = s.length();
        this.charArray = s.toCharArray();
        int leftRemoveCount = 0;
        int rightRemoveCount = 0;
        // 计算要删除的左括号的数量和右括号数量
        for (char c : charArray){
            if (c == '(') {
                leftRemoveCount++;
            } else if (c == ')') {
                if (leftRemoveCount == 0) {
                    rightRemoveCount++;
                } 
                if (leftRemoveCount > 0) {
                    leftRemoveCount--;
                }
                
            }
        }
        dfs(000, leftRemoveCount, rightRemoveCount, new StringBuilder());
        return new ArrayList<>(this.result);
        
    }

    // index 当前遍历的下标
    // leftCount 已经遍历的左括号的数量
    // rightCount 已经遍历的右括号的数量
    // leftRemoveCount 最少应该删除的左括号的数量
    // rightRemoveCount 最少应该删除的右括号的数量
    // path 中间结果
    private void dfs(int index, int leftCount, int rightCount, int leftRemoveCount, int rightRemoveCount, StringBuilder path){

        // 终止条件
        if (index == len) {
            if (leftRemoveCount == 0 && rightRemoveCount == 0) {
                result.add(path.toString());
            }
            return;
        }

        // 可能的操作1 删除当前的字符
        char currentChar = charArray[index];
        if(currentChar == '(' && leftRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount - 1, rightRemoveCount, path);
        }
        if (currentChar == ')' && rightRemoveCount > 0) {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount - 1, path);
        }
        // 可能的操作2将当前字符加入中间结果 
        path.append(currentChar);
        if (currentChar != '(' && currentChar != ')') {
            dfs(index + 1, leftCount, rightCount, leftRemoveCount, rightRemoveCount, path);
        } else if (currentChar == '(') {
            dfs(index + 1, leftCount + 1, rightCount, leftRemoveCount, rightRemoveCount, path);
        } else if (currentChar == ')' && rightCount < leftCount) {
            dfs(index + 1, leftCount, rightCount + 1, leftRemoveCount, rightRemoveCount, path);
        }
        // 回退
        path.deleteCharAt(path.length() - 1);
    }
}

Persistence

2021/04/03  阅读:39  主题:兰青

作者介绍

Persistence