20240226
正则表达式匹配(hot100 hard)
太难想到了，暴力过了2/3左右，粘贴leetcode解析便于复习
思路：动态规划
定义 dp[i][j]表示 s 的前 i 个字符和 p的前 j 个字符能否匹配,分以下几种情况讨论：
1、p[j] 是一个小写字母a-z，则 s[i]必须也为同样的小写字母方能完成匹配
2、p[j] 为'.'，则p[i]与s[j]一定能匹配上，因为p[j]可以与任意字母相等，即dp[i][j] = dp[i - 1][j - 1]
3、p[j] 为'*'，p[j]的前一个字符 p[j−1]匹配任意次(包括 0 次，p[j - 1]为'.'视作匹配)，此时从0开始举几个例子：
(1)匹配0次，则p[j - 1] != s[i]，则p字符串的0到j - 1位与s字符串的0到i位一定不匹配，此时应考虑p字符串的0到j - 2位
位与s字符串的0到i位的匹配性，即dp[i][j] = dp[i][j - 2];
(2)匹配1次，则p[j - 1] = s[i]，p字符串第j - 1到j位一定与s字符串的第i位长度为1的子串匹配（例如a与a*匹配，a*转化为a），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - 1位的匹配性，即dp[i][j] = dp[i - 1][j - 2];
(3)匹配2次，则p[j - 1] = s[i] = s[i - 1]，p字符串第j - 1到j位一定与s字符串第i - 1到i位匹配（例如aa与a*匹配，a*转化为aa），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - 2位的匹配性，即dp[i][j] = dp[i - 2][j - 2];
(4)以此类推，匹配k次，即p[j - 1] = s[i] = s[i - 1] = ... = s[i - k + 1]，则p字符串第j - k + 1到j位一定与s字符串第i - 1到i位匹配（例如aa...a(共k个a)与a*匹配，a*转化为aa...a(共k个a)），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - k位的匹配性，即dp[i][j] = dp[i - k][j - 2]。
图示如下：
优化方法如下：
因此此时dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i] = p[j - 1] || p[j - 1] = '.'))
初始条件：
AC代码：
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for(int i = 1; i <= n; i++){
if(p.charAt(i - 1) == '*'){
dp[0][i] = dp[0][i - 2];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'){
dp[i][j] = dp[i - 1][j - 1];
}else if(p.charAt(j - 1) == '*'){
dp[i][j] = dp[i][j - 2] | (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) | p.charAt(j - 2) == '.'));
}
}
}
return dp[m][n];
}
投递饿了么等公司8个岗位