class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}
}补充一个python的实现：
class Solution:
def isMatch(self, s: 'str', p: 'str') -> 'bool':
m,n = len(s),len(p)
#dp[i][j]表示s[:i+1]是否可以匹配p[:j+1]
dp = [[False for _ in range(n+1)]for _ in range(m+1)]
#前提，空白字符可以匹配空白规则
dp[0][0] = True
#如果有*，则*前的字符可以省略
for j in range(1,n+1):
if (p[j-1] == '*'):
dp[0][j] = dp[0][j-2] for i in range(1,m+1):
for j in range(1,n+1):
if s[i-1] == p[j-1]:#s与p的当前位置上相同
dp[i][j] = dp[i-1][j-1]#当前位置与左上角(同时去掉s和p的当前位置后)匹配性相同
elif p[j-1] == '.':#p当前位置是'.'，可以匹配任意1个字符
dp[i][j] = dp[i-1][j-1]#当前位置与左上角(同时去掉s和p的当前位置后)匹配性相同
elif p[j-1] == '*':#p当前位置是'*'，可以匹配任意0个、1个或多个字符
if s[i-1] == p[j-2]:#s与p的前一位置上相同
#假设s字符串是ba，p模式串是ba*
#(b->ba*) or (ba->ba) or (ba->b)
#这三种只要有一种是True，就说明可以匹配
dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
elif p[j-2] == '.':#再次使用 当前字符匹配性判断1
dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
else:
dp[i][j] = dp[i][j-2] return dp[m][n]
本题与剑指Offer 19 正则表达式匹配是同一道题。