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
backtracking
之前这题有不带*的情形，当时是用stack做的。那有了星号，我不知道怎么处理星号了。也想到能把三种情况都试一下，但是没想到怎么搞，就算这么做了，如果*太多，分叉的情况就会乘3再成3，复杂度很高吧，就没想下去了。看到别人用这个思路做了，回溯做的，没有超时。
我试着模仿了一下，遇到了很多问题：
1. 写成return dfs(s, count ++, start ++);
这么做IDE会提示你count, start的值没有被用到，我很疑惑。后来想通了，因为++在后面的时候，是执行完了当前语句再自增的，所以进入下一层循环回来之后再增加已经没卵用了。
2. 写成return dfs(s, ++count , ++start);
跟1不同的是，这么做虽然改变了count和start的值，但是这么做无异于先count ++再把count当作参数传入下一层递归，问题是这么做就没有恢复现场的-- 操作了。所以，只能count + 1这么做。递归的参数要慎用自增运算符。
public boolean checkValidString(String s) {
if (s == null || s.length() == 0) return true;
return dfs(s, 0, 0);
}
private boolean dfs(String s, int count, int start) {
if (count < 0)
return false;
if (start >= s.length())
return count == 0;
if (s.charAt(start) == '(') {
return dfs(s, count + 1, start + 1);
}
if (s.charAt(start) == ')') {
return dfs(s, count - 1, start +1);
}
if (s.charAt(start) == '*') {
//一旦遇到true就结束递归，一层层返回true
return dfs(s, count + 1, start + 1)
|| dfs(s, count - 1, start + 1)
|| dfs(s, count, start + 1);
}
return count == 0;
}
或写成：
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 == '*') {
return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
}
}
return count == 0;
}
}
One pass
看到一种O(n)的one pass解法，
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
} else if (s.charAt(i) == ')') {
if (low > 0) {
low--;
}
high--;
} else {
if (low > 0) {
low--;
}
high++;
}
if (high < 0) {
return false;
}
}
return low == 0;
}
当遇到*的时候，low要--同时high要++；
high is tracking maximum number of open braces possible '('.
if it encounters a *, it considers it as '('
low is tracking minimum number of open braces.
If it encounters a *, it considers it as ')'
In the end, if high is negative, that means there were too many ')'
If low < 0, it means there are more ')' than '(', which is invalid
https://discuss.leetcode.com/topic/103936/short-java-o-n-time-o-1-space-one-pass/6
不太懂，以后有机会再看吧
