题目
请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的那一个元素。
请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。
示例 1：
输入：article = “aa”, input = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：article = “aa”, input = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：
输入：article = “ab”, input = “."
输出：true
解释：".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。
提示：
1 <= article.length <= 20
1 <= input.length <= 20
article 只包含从 a-z 的小写字母。
input 只包含从 a-z 的小写字母，以及字符 . 和 * 。
保证每次出现字符 * 时，前面都匹配到有效的字符
代码
class Solution {
public boolean isMatch(String s, String p) {
if(s == null || p == null){
return true;
}
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n+1][m+1];
// 初始化
dp[0][0] = true;
for(int j = 2; j <= m; j++){
if(p.charAt(j - 1) == ‘*’){
dp[0][j] = dp[0][j - 2];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 当j不为 *
if(p.charAt(j - 1) != '*'){
// 如果不匹配
if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i - 1)){
dp[i][j] = dp[i-1][j-1];
}
} else {
// 第j-1个字符不匹配
if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j-2) != '.'){
dp[i][j] = dp[i][j-2];
} else {
dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
}
}
}
}
return dp[n][m];
}
}
时间复杂度：O(nm)
空间复杂度：O(nm)