题目描述
请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
示例1
输入
“aaa”,“a*a”
返回值
true
思路以及解答
这道题，仔细一想，感觉情况很多，很凌乱，此处介绍的是递归的做法，其实本题还可以使用动态规划。最重要的是需要分类讨论，原串定义为str,模式串为pattern。`
- 如果
pattern长度为0- 且
str长度为0,说明刚刚好匹配完，返回ture str长度不为0，说明没有匹配完，返回false
- 且
- 如果
pattern的长度大于0- 分为两种情况讨论，一种是直接把
*和*前面的字符去掉，相当于匹配了0个，然后接着比较；另外一种是，如果str的长度大于0，并且第一个字符匹配，那就把str的第一个字符去掉，两者接着匹配。 - 如果
pattern的长度大于1，且第2个字符是*，说明前面的字符可以匹配0，1或者多次 - 否则，说明第二个字符不是
*，那么就直接比较第一个字符是不是匹配，同时将后面的字符进行匹配。
- 分为两种情况讨论，一种是直接把
注意：上面说的第一个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为’.'的情况。
public boolean match(String str, String pattern) {
if (pattern.length() == 0) {
return str.length() == 0;
}
// 第二个字符是'*'
if (pattern.length() > 1 && pattern.charAt(1) == '*') {
// 匹配0次，直接把'*'去掉，两者判断
return match(str, pattern.substring(2))
// 第一个字符相同的时候，去掉第一个字符，判断后面的（相当于匹配多次）
|| (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern);
} else {
// 第二个字符不是 '*'的时候，判断第1个字符是否相同，相同的时候再从第2位开始比较
return str.length() > 0
&& firstSame(str, pattern)
&& (match(str.substring(1), pattern.substring(1)));
}
}
// 判断第一个字符是不是相同
private boolean firstSame(String s, String p) {
// 两个相同，或者有一个是"."
return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
}
当然，这种做法不是最优的，使用了大量的递归操作，并且重复递归，时间复杂度比较高。
当然，这道题还有一个更优的做法，但是过程咋一看有点复杂，我们可以来分析一下，主要思路是动态规划：
-
首先我们需要定义状态：用一个二维数组（套路）
dp[i][j]用来表示str的前i个字符和pattern的前j个字符是否匹配。 -
接下来，我们需要初始化简单状态，因为想要求后面的状态，是依赖于前面的状态的，一般是初始化
dp[i][j]的首行和首列。
dp[0][0]= true,表示两个空的字符串是匹配的。dp数组的首列，除了dp[0][0]为true，其他的都是false。因为pattern为空，但是s不为空的时候，肯定不匹配。dp的首行，也就是str为空的时候，如果pattern的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0次。
初始化前面之后，后面的从索引1开始匹配：
- 2.1 如果
dp[i - 1][j - 1]=trueandstr[i - 1] == pattern[j - 1]时，则dp[i][j]=true。（也就是前面匹配，接下来的字符一样匹配） - 2.2 如果
dp[i - 1][j - 1]=true且pattern[i-1]=='.'，那么dp[i][j]=true。(其实也是.可以匹配任何字符)
- 1.1 如果
dp[i][j-2]==true，那么dp[i][j]=true(相当于str的前i和pattern的前j-2个字符匹配，此时的*前面的那个字符出现了0次)。 - 1.2 如果
dp[i-1][j]==true且str[i-1]==pattern[j-2]，则dp[i][j] =true。（如果str的前i - 1个字符和pattern的前j个字符匹配，并且str的第i个字符和pattern的第j - 1个字符相等,相当于‘*’前面的字符出现了1次） - 1.3 如果
dp[i-1][j]=true且pattern[j-2]=='.'的时候，则dp[i][j]=true。(表示str的前i-1个和patten的前j个匹配，并且pattern的第j-1个是‘.’，第j个是‘*’,那么说明可以匹配任何字符任何次数，自然str可以多匹配一个字符。)
pattern的第j个字符不为“*”(即是pattern[j-1]！='*')pattern的第j个字符为“*”(即是pattern[j-1]=='*')
处理完数组之后，最后返回dp[n-1][m-1]，也就是str的前n个和pattern的前m个字符是否匹配。
public boolean match(String str, String pattern) {
if (pattern.length() == 0) {
return str.length() == 0;
}
int n = str.length() + 1;
int m = pattern.length() + 1;
boolean[][] dp = new boolean[n][m];
dp[0][0] = true;
for (int j = 2; j < m; j = j + 2) {
if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
dp[0][j] = true;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (pattern.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2]
|| dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2)
|| pattern.charAt(j - 2) == '.');
} else {
dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1)
|| pattern.charAt(j - 1) == '.');
}
}
}
return dp[n - 1][m - 1];
}
时间复杂度 O(mn) ： 其中 m,n 分别为 str 和 pattern 的长度，状态转移需遍历整个 dp 矩阵。
空间复杂度 O(mn)： 状态矩阵 dp 使用 O(mn)的额外空间。
