【力扣刷题】10. 正则表达式匹配
一、题目描述
来源:力扣（LeetCode）
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。提示：
1 <= s.length <= 201 <= p.length <= 30s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
二、思路分析
使用动态规划来解决：
首先确定状态，我们定义dp[i][j]：代表字符串s[0~(i-1)]和字符串p[0~(j-1)]的匹配状态，如果dp[i][j]==1,则说明s[0~(i-1)]能被p[0~(j-1)]匹配，反之，当dp[i][j]==0,则说明 s[0~(i-1)]不能被p[0~(j-1)]匹配。
接下来是初始化问题，dp[0][0]代表字符串s和字符串p都是空串，空串和空串肯定是能匹配的，所以dp[0][0] = 1；当只有字符串p是空串时，这时的字符串s和字符串p肯定是无法匹配的，所以dp[0.....n][0]=0；当只有字符串s是空串时，我们看下图的初始情况，ab，a*c*ab，其中a*，将会变成一个空串，所以在dp[0][2] = 1 ，它是由dp[0][0]决定的，这是一个状态转移，即当p[j-1] == '*'时，dp[0][j]=dp[0][j-2]。
最后考虑状态转移，
- 当指针指向的两个字符相等时，即
s[i-1]==p[j-1]或者p[j-1]=='.'（因为'.'可以匹配任意单字符），只有当dp[i-1][j-1]是匹配的，dp[i][j]才是匹配的，如下图中蓝色的位置，状态转移方程为dp[i][j] = dp[i-1][j-1]
- 当指针指向字符串p的
*时，即p[j-1]=='*'时，分两种情况
① s[i-1]!=p[j-2]&&p[j-2]!='.'，也就是kac,kb*ac，说明此时b*应该是一个空串，当是空串的转移方程前面提到过，dp[i][j]=dp[i][j-2]
② s[i-1]==p[j-2]||p[j-2]=='.'，此时的*可以匹配0个，一个，多个前面的元素
a.当*匹配前面0个元素，也就是空串喽~`dp[i][j]=dp[i][j-2]`
b.当*匹配前面一个元素时，也就是a,a*这种情况，只要字符串s*前面的匹配了就可以，状态转移为dp[i][j]=dp[i][j-1]
c.当*匹配前面多个元素时，也就是aaaa,a*这种情况，状态转移为dp[i][j]=dp[i-1][j]
三、代码实现
class Solution {
public boolean isMatch(String s, String p) {
char[] cs = s.toCharArray();
char[] cp = p.toCharArray();
// dp[i][j]:表示s的前i个字符，p的前j个字符是否能够匹配
boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
// 初期值
// s为空，p为空，能匹配上
dp[0][0] = true;
// p为空，s不为空，必为false(boolean数组默认值为false，无需处理)
// s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
for (int j = 1; j <= cp.length; j++) {
if (cp[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// 填格子
for (int i = 1; i <= cs.length; i++) {
for (int j = 1; j <= cp.length; j++) {
// 文本串和模式串末位字符能匹配上
if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (cp[j - 1] == '*') { // 模式串末位是*
// 模式串*的前一个字符能够跟文本串的末位匹配上
if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
dp[i][j] = dp[i][j - 2] // *匹配0次的情况
|| dp[i - 1][j]; // *匹配1次或多次的情况
} else { // 模式串*的前一个字符不能够跟文本串的末位匹配
dp[i][j] = dp[i][j - 2]; // *只能匹配0次
}
}
}
}
return dp[cs.length][cp.length];
}
}四、运行结果
总结
这是一个经典的动态规划问题，在面试中经常考到，值得反复练习~