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 思路
代码
1 class Solution { 2 public boolean checkValidString(String s) { 3 return check(s, 0, 0); 4 } 5 6 private boolean check(String s, int start, int count) { 7 if (count < 0) return false; 8 9 for (int i = start; i < s.length(); i++) { 10 char c = s.charAt(i); 11 if (c == '(') { 12 count++; 13 } 14 else if (c == ')') { 15 if (count <= 0) return false; 16 count--; 17 } 18 else if (c == '*') { 19 //1. * for '(' --> (*)) 20 //2. * for ')' --> ((*) 21 //3. * for empty string --> (*) 22 return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count); 23 } 24 } 25 26 return count == 0; 27 } 28 29 }
转载于:https://www.cnblogs.com/liuliu5151/p/9828167.html
