[LeetCode] 678. Valid Parenthesis String
文章目录
Problem
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
Note:
The string size will be in the range [1, 100].
Solution
class Solution {
public boolean checkValidString(String s) {
return helper(s, 0, 0);
}
private boolean helper(String s, int index, int count) {
if (index == s.length()) {
return count == 0;
}
if (count < 0) return false;
char ch = s.charAt(index);
if (ch == '(') return helper(s, index+1, count+1);
else if (ch == ')') return helper(s, index+1, count-1);
else return helper(s, index+1, count-1) || helper(s, index+1, count+1) || helper(s, index+1, count);
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论