题目大意：
有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
- * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
- 一个空字符串也被视为有效字符串。
示例 1:
输入: "()" 输出: True
示例 2:
输入: "(*)" 输出: True
示例 3:
输入: "(*))" 输出: True
注意:
- 字符串大小将在 [1，100] 范围内。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=678
解题思路分析：
这道题可以使用动态规划来解题。当然也可以使用递归加记忆数组的方式。最终如果想使得字符串有效，就要保证正括号与反括号的个数相同，并且对于字符串的任意一个前缀子串，都要保证正括号个数大于等于反括号个数。
解题时，我们建立一个递归函数，参数为当前递归到字符串的下标位置，以及当前为止正括号的个数。递归函数的返回值为从当前位置到字符串尾部是否是有效字符串。递归函数中，如果当前字符是正括号，那么我们将正括号个数加一，同时将下标加一递归到子问题去求解。同理如果当前字符是反括号，那么我们将正括号个数减一，同时将下标加一递归到子问题去求解。如果当前字符是星号，那么星号可以代表正括号，反括号或者空字符三种可能。我们将对应的这三种可能分别递归至子函数，三种可能中有一种方式的结果为真即可。最终递归函数的终止条件是，当下标越界时，如果正括号个数正好为0返回true，反之返回false。另外当正括号个数小于0时，返回false。
最后再考虑记忆数组（相当于动态规划中的DP数组）。记忆数组的定义很简单，我们只需要查看递归函数中的可变参数即可。本题中，存在当前下标以及正括号个数两个可变参数，因此定义一个2维数组即可。
实现代码：
Boolean[][] memo; // 记忆数组
public boolean checkValidString(String s) {
memo=new Boolean[s.length()][s.length()]; // 初始化记忆数组
char[] arr=s.toCharArray(); // 为了提高效率，将字符串转为字符数组
return help(arr,0,0); // 递归求解
}
boolean help(char[] arr, int index, int leftCount){
// 如果正括号个数小于0，返回false
if(leftCount<0) return false;
// 当下标越界时，如果正括号个数正好为0，返回true
if(index==arr.length) return leftCount==0;
// 如果记忆数组中存在当前解，返回记忆数组中的数值
if(memo[index][leftCount]!=null) return memo[index][leftCount];
// 当前字符
char c = arr[index];
// 返回结果
boolean res = false;
// 如果当前字符是正括号
if(c=='(') res= help(arr,index+1,leftCount+1);
// 如果当前字符是反括号
else if(c==')') res= help(arr,index+1,leftCount-1);
// 如果当前字符是星号
else{
res= help(arr,index+1,leftCount) // 星号作为空字符
|| help(arr,index+1,leftCount+1) // 星号作为正括号
|| help(arr,index+1,leftCount-1); // 星号作反正括号
}
// 将当前结果存入记忆数组
memo[index][leftCount] = res;
return res;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Parenthesis String.
Memory Usage: 39.2 MB, less than 5.00% of Java online submissions for Valid Parenthesis String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-678-valid-parenthesis-string-解题思路分析/