678. Valid Parenthesis String 发表于 2022-02-03 DP1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution { public boolean checkValidString(String s) { int n = s.length(); // 定义 dp[i][j] 为字符串 s[i, j] 是否为有效的括号字符串 // dp[i][j] depends on dp[i + 1][j - 1] // dp[i][j] depends on dp[i][k] & dp[k + 1][j] boolean[][] dp = new boolean[n][n]; // when sub str length = 1 for (int i = 0; i < n; i++) { if (s.charAt(i) == '*') { dp[i][i] = true; } } // when sub str length = 2 for (int i = 0; i < n - 1; i++) { char a = s.charAt(i), b = s.charAt(i + 1); if ((a == '(' || a == '*') && (b == ')' || b == '*')) { dp[i][i + 1] = true; } } // when sub str length >= 3 for (int i = n - 3; i >= 0; i--) { char a = s.charAt(i); if (a == ')') { continue; } for (int j = i + 2; j < n; j++) { char b = s.charAt(j); if (b == '(') { continue; } dp[i][j] |= dp[i + 1][j - 1]; for (int k = i; k < j && !dp[i][j]; k++) { dp[i][j] = dp[i][k] && dp[k + 1][j]; } } } return dp[0][n - 1]; }} Stack12345678910111213141516171819202122232425262728293031323334353637class Solution { public boolean checkValidString(String s) { Stack<Integer> leftBracketStack = new Stack<>(); Stack<Integer> asteriskStack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { leftBracketStack.push(i); } else if (c == ')') { if (!leftBracketStack.isEmpty()) { leftBracketStack.pop(); } else if (!asteriskStack.isEmpty()) { asteriskStack.pop(); } else { return false; } } else { // c == '*' asteriskStack.push(i); } } while (!leftBracketStack.isEmpty()) { if (asteriskStack.isEmpty()) { return false; } int leftBracketIndex = leftBracketStack.pop(); int asteriskIndex = asteriskStack.pop(); if (asteriskIndex < leftBracketIndex) { return false; } } return true; }} Greedy12345678910111213141516171819202122232425262728class Solution { public boolean checkValidString(String s) { int leftMin = 0, leftMax = 0; // 剩余的左括号数量的上界与下界:[leftMin, leftMax] for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { leftMin++; leftMax++; } else if (c == ')') { // 此时可抵消一个左括号,但是左括号下界为 0 时不能抵消左括号,此时可以选择抵消 '*', 若 '*' 不足则直接返回 false leftMin = Math.max(leftMin - 1, 0); leftMax--; if (leftMax < 0) { return false; } } else { // c == '*' // 充当右括号时,若此时没有左括号了,如字符串 "*",则不能抵消左括号,所以需要保持 leftMin 为 0 leftMin = Math.max(leftMin - 1, 0); // 充当左括号时 leftMax++; } } return leftMin == 0; // 左括号是否能被匹配完 }} Reference678. Valid Parenthesis String