My solution for this problem is using two stacks, it's very easy to understand:
public boolean checkValidString(String s) { Stack<Integer> stars = new Stack<>(); Stack<Integer> stk = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '*') stars.push(i); else if (s.charAt(i) == '(') stk.push(i); else { if (!stk.isEmpty()) stk.pop(); else if (!stars.isEmpty()) stars.pop(); else return false; } } while (!stk.isEmpty()) { if (!stars.isEmpty()) { if (stk.pop() > stars.pop()) return false; } else return false; } return true; }
网友的算法,不太好理解,但是算法很好:
public boolean checkValidString2(String s) { int cmin = 0, cmax = 0; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if (c == '(') { cmax++; cmin++; } else if (c == ')') { cmax--; cmin = Math.max(cmin - 1, 0); } else { cmax++; cmin = Math.max(cmin - 1, 0); } if (cmax < 0) return false; } return cmin == 0; }