栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode

目录
  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

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

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

示例 1:
输入:s = “()())()”
输出:[“(())()”,“()()()”]

示例 2:
输入:s = “(a)())()”
输出:[“(a())()”,“(a)()()”]

示例 3:
输入:s = “)(”
输出:[“”]

提示:
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-invalid-parentheses

2.思路

(1)回溯
思路参考本题官方题解。

3.代码实现(Java)
//思路1————回溯
public class Solution {
    //存放所有可能的结果
    List res = new ArrayList();
    
    public List removeInvalidParentheses(String s) {
        int lremove = 0;
        int rremove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                lremove++;
            } else if (s.charAt(i) == ')') {
                if (lremove == 0) {
                    rremove++;
                } else {
                    lremove--;
                }
            }
        }
        backtrace(s, 0, lremove, rremove);
        return res;
    }
    
    public void backtrace(String str, int start, int lremove, int rremove) {
        if (lremove == 0 && rremove == 0) {
            if (isValid(str)) {
                res.add(str);
            }
            return;
        }
        for (int i = start; i < str.length(); i++) {
            if (i != start && str.charAt(i) == str.charAt(i - 1)) {
                continue;
            }
            //剪枝操作:如果剩余的字符无法满足去掉的数量要求,直接返回
            if (lremove + rremove > str.length() - i) {
                return;
            }
            //尝试去掉一个左括号
            if (lremove > 0 && str.charAt(i) == '(') {
                backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);;
            }
            //尝试去掉一个右括号
            if (rremove > 0 && str.charAt(i) == ')') {
                backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
            }
        }
    }
    
    //判断字符串 str 中的括号是否有效
    public boolean isValid(String str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
            } else if (str.charAt(i) == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }
        return cnt == 0;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937313.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号