10. 正则表达式匹配

---

前言

`
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

样本对应模型
定义二维表
字符串有效性检查
str不能有.和*
exp开头不能是*.两个*不能挨着

	public static boolean isValid(char[] s, char[] e) {
    
		// s中不能有'.' or '*'
		for (int i = 0; i < s.length; i++) {
    
			if (s[i] == '*' || s[i] == '.') {
    
				return false;
			}
		}
		// 开头的e[0]不能是'*'，没有相邻的'*'
		for (int i = 0; i < e.length; i++) {
    
			if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
    
				return false;
			}
		}
		return true;
	}

暴力递归

递归含义:
str从si出发及其后面的所有,能不能被exp从ei出发及其后面的所有配出来
能配出来返回true,否则false

1. ei下一个位置不是*
   如果ei+1不是 * ，就说明我e没有操作空间了。它不能指望后面的 * 把它变没,代表此时si必须能和ei对上
   只能是[ei]字符等于[si]字符
   要么[ei]字符是 . ,它能够变成一切

2. ei+1是*
   0)变零个
   

让a*变0个a,后面去匹配
1)变1个a
2)变2个a
3) 3个a
4) 4个a

每一种分支全都走，但有一个走通，直接返回true,所有分支都走不通，返回false,

	public static boolean isMatch1(String str, String exp) {
    
		if (str == null || exp == null) {
    
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		return isValid(s, e) && process(s, e, 0, 0);
	}

	// str[si.....] 能不能被 exp[ei.....]配出来！ true false
	public static boolean process(char[] s, char[] e, int si, int ei) {
    
		if (ei == e.length) {
     // exp 没了 str？
			return si == s.length;
		}
		// exp[ei]还有字符
		// ei + 1位置的字符，不是*
		if (ei + 1 == e.length || e[ei + 1] != '*') {
    
			// ei + 1 不是*
			// str[si] 必须和 exp[ei] 能配上！
			return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
		}
		// exp[ei]还有字符
		// ei + 1位置的字符，是*!
		while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
    
			if (process(s, e, si, ei + 2)) {
    
				return true;
			}
			si++;
		}
		return process(s, e, si, ei + 2);
	}

斜率优化+记忆化搜索

f(13, 29)的依赖

f(12, 29)的依赖
f(12, 29)=f(13,29)+f(12,31)
在str中i位置字符和str中i+ 1位置字符它一样的时候就存在这个优化

当我一-个格子有枚举行为的时候，我就观察他已经算过的格子,能不能把枚举行为替代掉,
从而得到一一个使用有限若干个位置的方式来得到这一个格子的值

	public static boolean isMatch2(String str, String exp) {
    
		if (str == null || exp == null) {
    
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		if (!isValid(s, e)) {
    
			return false;
		}
		int[][] dp = new int[s.length + 1][e.length + 1];
		// dp[i][j] = 0, 没算过！
		// dp[i][j] = -1 算过，返回值是false
		// dp[i][j] = 1 算过，返回值是true
		return isValid(s, e) && process2(s, e, 0, 0, dp);
	}

	public static boolean process2(char[] s, char[] e, int si, int ei, int[][] dp) {
    
		if (dp[si][ei] != 0) {
    
			return dp[si][ei] == 1;
		}
		boolean ans = false;
		if (ei == e.length) {
    
			ans = si == s.length;
		} else {
    
			if (ei + 1 == e.length || e[ei + 1] != '*') {
    
				ans = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process2(s, e, si + 1, ei + 1, dp);
			} else {
    
				if (si == s.length) {
     // ei ei+1 *
					ans = process2(s, e, si, ei + 2, dp);
				} else {
     // si没结束
					if (s[si] != e[ei] && e[ei] != '.') {
    
						ans = process2(s, e, si, ei + 2, dp);
					} else {
     // s[si] 可以和 e[ei]配上
						ans = process2(s, e, si, ei + 2, dp) || process2(s, e, si + 1, ei, dp);
					}
				}
			}
		}
		dp[si][ei] = ans ? 1 : -1;
		return ans;
	}