algorithm-class/算法周更班/class_2022_07_3_week/Code02_ValidParenthesisString.java

package class_2022_07_3_week;

// 来自蔚来汽车
// 给定一个只包含三种字符的字符串：( 、) 和 *，
// 写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
// 任何左括号 ( 必须有相应的右括号 )。
// 任何右括号 ) 必须有相应的左括号 ( 。
// 左括号 ( 必须在对应的右括号之前 )。
// * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符。
// 一个空字符串也被视为有效字符串。
// 测试链接 : https://leetcode.cn/problems/valid-parenthesis-string/
public class Code02_ValidParenthesisString {

	public static boolean valid(String str) {
		char[] s = str.toCharArray();
		int n = s.length;
		int[][] dp = new int[n][n + 1];
		// dp[i][j] == 0 没算过！
		// dp[i][j] == -1 算过了！结果是false！
		// dp[i][j] == 1 算过了！结果是true！
		return zuo(s, 0, 0, dp);
	}

	public static boolean zuo(char[] s, int i, int c, int[][] dp) {
		if (i == s.length) {
			return c == 0;
		}
		if (c < 0) {
			return false;
		}
		if (dp[i][c] != 0) {
			return dp[i][c] == 1;
		}
		boolean ans = false;
		if (s[i] == '(') {
			ans = zuo(s, i + 1, c + 1, dp);
		} else if (s[i] == ')') {
			ans = zuo(s, i + 1, c - 1, dp);
		} else { // *
			boolean p1 = zuo(s, i + 1, c + 1, dp);
			boolean p2 = zuo(s, i + 1, c - 1, dp);
			boolean p3 = zuo(s, i + 1, c, dp);
			ans = p1 || p2 || p3;
		}
		dp[i][c] = ans ? 1 : -1;
		return ans;
	}

	// 时间复杂度O(N平方)
	// 从左往右的尝试
	// 暴力递归改动态规划
	public static boolean checkValidString1(String s) {
		char[] str = s.toCharArray();
		int n = str.length;
		int[][] dp = new int[n][n];
		return f(str, 0, 0, dp);
	}

	public static boolean f(char[] s, int i, int c, int[][] dp) {
		if (i == s.length) {
			return c == 0;
		}
		if (c < 0) {
			return false;
		}
		if (c > s.length - i) {
			return false;
		}
		if (dp[i][c] != 0) {
			return dp[i][c] == 1;
		}
		boolean ans = false;
		if (s[i] == '(') {
			ans = f(s, i + 1, c + 1, dp);
		} else if (s[i] == ')') {
			ans = f(s, i + 1, c - 1, dp);
		} else {
			ans |= f(s, i + 1, c + 1, dp);
			ans |= f(s, i + 1, c - 1, dp);
			ans |= f(s, i + 1, c, dp);
		}
		dp[i][c] = ans ? 1 : -1;
		return ans;
	}

	// 贪心方法
	// 最优解
	// 时间复杂度O(N)，额外空间复杂度O(1)
	public static boolean checkValidString2(String s) {
		char[] str = s.toCharArray();
		int max = 0;
		int min = 0;
		for (char x : str) {
			if (x == '(') {
				max++;
				min++;
			} else {
				// )  *
				if (x == ')' && max == 0) { // 不够减了!
					return false;
				}
				// max 够减
				// ) *
				// max -1  +1
				max += x == ')' ? -1 : 1;
				// min ( - ) 弹性范围中，最小的差值
				// ) * min -1
				// min == 0
				if (min > 0) {
					min--;
				}
			}
		}
		// 0 ~ 7
		// 3 ~ 9
		return min == 0;
	}

}