leetcode 678有效的括号字符串

冷不防 2023-07-01 12:58 9阅读 0赞

给定一个只包含三种字符的字符串：（ ，） 和 \*，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。  
任何右括号 ) 必须有相应的左括号 ( 。  
左括号 ( 必须在对应的右括号之前 )。

*  可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。  
    一个空字符串也被视为有效字符串。  
    示例 1:

输入: “()”  
输出: True  
示例 2:

输入: “(\*)”  
输出: True  
示例 3:

输入: “(\*))”  
输出: True  
注意:

字符串大小将在 \[1，100\] 范围内。

思路：  
1.贪心法处理，即用2个变量记录，左扩号的数量.  
这种方法十分高效，值得借鉴。

int l = 0;  // 代表左括号数量很多，匹配*作为右括号
    int r = 0;  // 代表左括号数量很少，匹配的*作为左括号

public boolean checkValidString(String s) {
        
            int l = 0;
            int r = 0;
            for (int i = 0;i < s.length();i++) {
        
                char t = s.charAt(i);
                if (t == '(') {
        
                    l++;
                    r++;
                } else if (t == ')') {
        
                    if (l > 0) l--;
                    r--;
                    if (r < 0) return false;
                } else if (t == '*') {
        
                    if (l > 0) l--; // *匹配为) l--;
                    r++;   // *匹配为 （  r++;
                }
            }
            return l == 0;   //最后满足匹配吗？
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

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

一、题目描述 ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_colo

快来打我*/ 2023年10月01日 21:11/ 0 赞/ 15 阅读

相关 Java实现 LeetCode 678 有效的括号字符串(暴力+思路转换)

678. 有效的括号字符串给定一个只包含三种字符的字符串：（，）和 \，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：任何左括号 ( 必须

青旅半醒/ 2023年07月22日 03:56/ 0 赞/ 10 阅读

相关 leetcode 678有效的括号字符串

给定一个只包含三种字符的字符串：（，）和 \，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：任何左括号 ( 必须有相应的右括号 )。任何右括

冷不防/ 2023年07月01日 12:58/ 0 赞/ 10 阅读

相关 LeetCode 20. 有效的括号（栈、字符串）

上一篇博客：[LeetCode 14.最长公共前缀（字符串）][LeetCode 14.] > 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted

矫情吗；*/ 2022年11月28日 10:45/ 0 赞/ 169 阅读

相关【字符串/栈】有效的括号（leetcode20）

一、题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

桃扇骨/ 2022年10月19日 00:48/ 0 赞/ 249 阅读

相关 Leetcode刷题100天—678. 有效的括号字符串( 字符串)—day36

前言： > 作者：神的孩子在歌唱 > > 大家好，我叫运智 ![image-20210912124448740][] [678. 有效的括号字符串][678.]

╰半橙微兮°/ 2022年09月14日 02:16/ 0 赞/ 164 阅读

相关 leetcode678. 有效的括号字符串

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5

淩亂°似流年/ 2022年09月11日 04:11/ 0 赞/ 173 阅读

相关 678 有效的括号字符串（括号匹配）

1. 问题描述：给定一个只包含三种字符的字符串：（，）和 \，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：任何左括号 ( 必须有相应的右括

「爱情、让人受尽委屈。」/ 2022年09月03日 00:14/ 0 赞/ 164 阅读

相关 leetcode 678. Valid Parenthesis String 有效括号的判断 + 保存index遍历

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘\’, write a func

梦里梦外;/ 2022年06月03日 08:24/ 0 赞/ 92 阅读

相关 LeetCode——有效的括号

题目：给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串，判断字符串是否有效。有效字符串需满足： 1. 左括号必须用相

分手后的思念是犯贱/ 2022年05月20日 10:10/ 0 赞/ 223 阅读