正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 **整个 **字符串s的，而不是部分字符串。
说明:
-
s可能为空，且只包含从a-z的小写字母。 -
p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入:
s ="aa"
p ="a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s ="aa"
p ="a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次
示例 3:
输入:
s ="ab"
p =".*"
输出: true
解释: "." 表示可匹配零个或多个（''）任意字符（'.'）
示例 4:
输入:
s ="aab"
p ="c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"
示例 5:
输入:
s ="mississippi"
p ="mis*is*p*."
输出: false
方法一：回溯
public boolean isMatch(String s, String p) {
if (p.isEmpty()) {
return s.isEmpty();
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (1 < p.length() && p.charAt(1) == '*') {
return isMatch(s, p.substring(2))//跳过与*前面的字符比较，即认为出现次数为0
|| firstMatch && isMatch(s.substring(1), p);
} else {
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
方法二：备忘录法（避免重复计算）
dp[i][j]表示s[i:],p[j:]能否匹配
时间复杂度O(TP) 用 T 和 P 分别表示匹配串和模式串的长度
public boolean isMatch(String s, String p) {
int[][] dp=new int[s.length()+1][p.length()+1];//0：默认 -1：不匹配 1：匹配
return helper(s,p,dp,0,0);
}
public boolean helper(String s,String p,int[][] dp,int i,int j){
if (p.isEmpty()) {
return s.isEmpty();
}
if(dp[i][j]!=0){
return dp[i][j]==1;
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
boolean ans;
if (1 < p.length() && p.charAt(1) == '*') {
ans= helper(s, p.substring(2),dp,i,j+2)//跳过与*前面的字符比较，即认为出现次数为0
|| firstMatch && helper(s.substring(1), p,dp,i+1,j);
} else {
ans= firstMatch && helper(s.substring(1), p.substring(1),dp,i+1,j+1);
}
if(ans){
dp[i][j]=1;
} else {
dp[i][j]=-1;
}
return ans;
}
方法三：动态规划(自底向上）
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[s.length()][p.length()] = true;
for (int i = s.length(); i >= 0; i--) {
for (int j = p.length()-1; j >= 0; j--) {
boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
dp[i][j] = dp[i][j + 2] || firstMatch && dp[i + 1][j];
} else {
dp[i][j] = firstMatch && dp[i+1][j+1];
}
}
}
return dp[0][0];
}
第二次做
递归
public boolean isMatch(String s, String p) {
return isMatch(s, p, 0, 0);
}
public boolean isMatch(String s, String p, int i, int j) {
if (j == p.length()) {
return i == s.length();
}
boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
return firstMatch && isMatch(s, p, i + 1, j) || isMatch(s, p, i, j + 2);
}
return firstMatch && isMatch(s, p, i + 1, j + 1);
}
备忘录
public boolean isMatch(String s, String p) {
return isMatch(s, p, 0, 0, new int[s.length() + 1][p.length() + 1]);
}
public boolean isMatch(String s, String p, int i, int j, int[][] dp) {
if (j == p.length()) {
return i == s.length();
}
if (dp[i][j] != 0) {
return dp[i][j] == 1;
}
boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
boolean isMatch;
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
isMatch = firstMatch && isMatch(s, p, i + 1, j, dp) || isMatch(s, p, i, j + 2, dp);
} else {
isMatch = firstMatch && isMatch(s, p, i + 1, j + 1, dp);
}
dp[i][j] = isMatch ? 1 : -1;
return isMatch;
}
动态规划
- s(i)=p(j)||p(j)='.' dp[i][j]=dp[i-1][j-1]
- p(j)='*' & s(i)!=p(j-1) dp[i][j]=dp[i][j-2]
- p(j)='*' & (s(i)==p(j-1)||p(j-1)='.') dp[i][j]=dp[i][j-2] || dp[i-1][j]
- 其它 dp[i][j]=false
注意初始值：
- dp[0][0]=true，表示都为空时相等
- p(j)='*'，可能与空串匹配，dp[0][j]=dp[0][j-2]
public boolean isMatch(String s, String p) {
int len1 = s.length();
int len2 = p.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 1; i < len2; i++) {
if (p.charAt(i) == '*') {
dp[0][i + 1] = dp[0][i - 1];
}
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
char c1 = s.charAt(i);
char c2 = p.charAt(j);
if (c1 == c2 || c2 == '.') {
dp[i + 1][j + 1] = dp[i][j];
} else if (c2 == '*') {
if (c1 == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i][j + 1];
} else {
dp[i + 1][j + 1] = dp[i + 1][j - 1];
}
}
}
}
return dp[len1][len2];
}
