有效的括号字符串.力扣678

快来打我* 2023-10-01 21:11 24阅读 0赞

## 一、题目描述 ##

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 二、思路 ##

题目中给出字符串中只含有 '(' , '\*' , ')' 三种，对于输入的字符串无非就是三种情况：

1.左括号（或\*） 等于 右括号（或\*）数量相等，返回true

2.左括号（或\*） 大于 右括号（或\*）数量相等，返回false

3.左括号（或\*） 小于 右括号（或\*）数量相等，返回false

步骤：

1.这里我们定义两个初始值为0的变量，一个代表左括号较多时，\*代表右括号时左括号的数量l；另一个代表右括号较多时，\*代表左括号时左括号的数量h。

2.然后使用charAt()遍历字符串，遍历到 '(' 时,l++ ,h++；遍历到 ')' 时，h--，如果\*代表左括号时左括号数量 > 0,l--；当遍历到 '\*' 时，\*代表左括号时的左括号数量h++,如果\*代表右括号时左括号数量的l不为空，l--。 当\*代表左括号时左括号数量小于0时，返回false。

3.遍历完成后返回 l == 0。

## 三、代码实现 ##

class Solution {
        public boolean checkValidString(String s) {
            int l = 0;  //l代表左括号比较多，星号作为右括号时左括号的数量
            int h = 0;  //h代表右括号比较多，星号作为左括号时左括号的数量
            for (int i = 0; i < s.length(); i++) {
                char tmp = s.charAt(i);
                if (tmp == '(') { // ( l和h都增加
                    l++;
                    h++;
                } else if (tmp == ')') { // ） 如果l不为空，说明左括号比较多，则l--.同时因为h也是代表左括号的数量，所以相应的h--
                    if (l > 0) {
                        l--;
                    }
                    h--;
                } else if (tmp == '*') { // * 如果l不为空，说明左括号比较多，星号作为右括号则l--.同时h是星号作为左括号，所以h++
                    if (l > 0) {
                        l--;
                    }
                    h++;
                }
                if (h < 0) { // h < 0.说明将*当做左括号也不够，返回false
                    return false;
                }
            }
            return l == 0; //  同时查看l == 0，如果不等于0，说明将星号视为右括号也不够左括号数量。
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/bacb7d99016d46b18352d6ca6f18008a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16