来源:力扣(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 <= 20
1 <= p.length <= 30
s
只包含从 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[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];
}
}
这是一个经典的动态规划问题,在面试中经常考到,值得反复练习~