[leetcode]678. Valid Parenthesis String验证有效括号字符串
2024-10-15 21:37:21
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
- Any left parenthesis
'('
must have a corresponding right parenthesis')'
. - Any right parenthesis
')'
must have a corresponding left parenthesis'('
. - Left parenthesis
'('
must go before the corresponding right parenthesis')'
. '*'
could be treated as a single right parenthesis')'
or a single left parenthesis'('
or an empty string.- An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
题目
验证有效括号字符串
思路
recursion
类似Leetcode 22 Generate Parenthesis 思路
代码
class Solution {
public boolean checkValidString(String s) {
return check(s, 0, 0);
} private boolean check(String s, int start, int count) {
if (count < 0) return false; for (int i = start; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
count++;
}
else if (c == ')') {
if (count <= 0) return false;
count--;
}
else if (c == '*') {
//1. * for '(' --> (*))
//2. * for ')' --> ((*)
//3. * for empty string --> (*)
return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
}
} return count == 0;
} }
最新文章
- db2无法force掉备份连接的处理办法
- tar 解压缩命令详解
- C++_STL
- Extract Stylish styles and save as JSON format
- iOS /* */多个嵌套解决
- 【python cookbook】【字符串与文本】6.以不区分大小写的方式对文本做查找和替换
- HDU 4825-Xor Sum(trie)
- eclipse快捷键(转载)
- 轻松驾驭Tomcat
- Dynamics CRM2013 附件禁用方案
- spiral matrix 螺旋矩阵
- Android第三次作业
- Cow Relays POJ - 3613 (floyd+快速幂)
- 2月第3周业务风控关注|上海网信办复测23个被约谈APP 涉及1号店、小红书等
- Angular基础(六) DI
- 07LaTeX学习系列之---Latex源文件的结构
- c# WPF 设置窗口一直在其中窗口后面/底层窗口
- Android常用逆向工具+单机游戏破解
- RocketMQ 消息存储
- Linux第二周学习总结——操作系统是如何工作的