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

括号匹配问题:判断一个字符串是否为有效的括号匹配

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

括号匹配问题:判断一个字符串是否为有效的括号匹配

括号匹配问题:判断一个字符串是否为有效的括号匹配?

提示:系列括号匹配问题


文章目录
  • 括号匹配问题:判断一个字符串是否为有效的括号匹配?
    • @[TOC](文章目录)
  • 题目
  • 一、审题
  • 从左往右记录左右括号的数量,对消,如果最后无法对冲,那就是有问题
  • 总结
题目

括号匹配有效的的情况:
有一个左,必然有一个右
每一个左与一个右匹配

问:如何判断一个字符串是有效的括号匹配?


一、审题

示例:()
(())
(()())
下面都不是有效的
(
)()
(()()


从左往右记录左右括号的数量,对消,如果最后无法对冲,那就是有问题

count=0
如果遇到(,count+=
如果遇到),count–

途中要是发现count<0提前说明)多一个,且,左边没法匹配
最后发现count不为0的话,显然没法匹配,不管是)多了,还是(多了

手撕代码:

    //复习:
    public static boolean isValidReview(String s){
        if (s.compareTo("") == 0 || s.length() == 0) return true;

        char[] str = s.toCharArray();
        int N = str.length;

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (str[i] == '(') count++;
            else count--;//遇到)

            if (count < 0) return false;//提前说明)过多了
        }

        return count == 0 ? true : false;//非0false
    }

    public static void test(){
        String s = "())(()))(";//需要补3个
        System.out.println(isValid(s));
        System.out.println(isValidReview(s));
        System.out.println(addNeedBracket(s));
    }

    public static void main(String[] args) {
        test();
    }

问题不大:

false
false

总结

提示:重要经验:

1)括号匹配本质就是看左右括号的数量是否一直,而且,)有括号还不能提前多出现!
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950653.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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