平衡括号(四)——会让你怀疑自己没学过平衡括号平衡括号(四)—

LeetCode_678_ValidParenthesisString
题目分析：
解法一：暴力

/** * 递归法暴力遇到* 将*的三种情况都带入 */ public static boolean checkValidString(String s) { return helper(s, 0, 0); }public static boolean helper(String s, int start, int cnt) { if (cnt < 0) return false; for (int i = start; i < s.length(); ++i) { if (s.charAt(i) == '(') { ++cnt; } else if (s.charAt(i) == ')') { if (cnt <= 0) return false; --cnt; } else { return helper(s, i + 1, cnt) || helper(s, i + 1, cnt + 1) || helper(s, i + 1, cnt - 1); } } return cnt == 0; }

解法二：两个栈

/** * '('和*分别压栈 * 遇到')'弹'(''('弹完弹'*' * 最后如果left star 都不为空区分*) 和 *(两个模式如果后者模式即存在栈顶的*在一个'('左方 false * 如果最终left用完 true 否则说明(右方的星号不够用 */ public static boolean checkValidString2(String s) { Stack left = new Stack<>(); Stack star = new Stack<>(); for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == '*') star.push(i); else if (s.charAt(i) == '(') left.push(i); else { if (left.empty() && star.empty()) return false; if (!left.empty()) left.pop(); else star.pop(); } } while (!left.empty() && !star.empty()) { if (left.peek() > star.peek()) return false; left.pop(); star.pop(); } return left.empty(); }

解法三：来回走两遍

/** * 正反两遍 * 正时将*当'(' * 反时将*当')' */ public static boolean checkValidString3(String s) { int left = 0, right = 0, n = s.length(); for (int i = 0; i < n; ++i) { if (s.charAt(i) == '(' || s.charAt(i) == '*') ++left; else --left; if (left < 0) return false; } if (left == 0) return true; for (int i = n - 1; i >= 0; --i) { if (s.charAt(i) == ')' || s.charAt(i) == '*') ++right; else --right; if (right < 0) return false; } return true; }

【平衡括号(四)——会让你怀疑自己没学过平衡括号】解法四：左括号上下限

/** * low high 分别代表遍历过程中可存在的左括号个数的下限和上限 * 上限 < 0 false */ public static boolean checkValidString4(String s) { int low = 0, high = 0; for (char c : s.toCharArray()) { if (c == '(') { ++low; ++high; } else if (c == ')') { if (low > 0) --low; --high; } else { if (low > 0) --low; ++high; } if (high < 0) return false; } return low == 0; }