通配符匹配
问题描述：
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wildcard-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。递归
首先定义fun(i，j)返回s从 i 开始，p从 j 开始能否匹配的上。
对当前元素s[i] 和 p[j] 分情况讨论，
若s[i] 恰好等于p[j]，或者p[j]为 ‘?’时，fun(i, j)的求解就可以转化为对 fun(i + 1, j + 1)的求解；
若p[i]即不为’?’ ‘*’这些，又不等于s[i]，s从i开始p从j开始无论如何也匹配不上；
剩下就只有p[j] 为 ’*‘这种可能了，依次让p[j] 匹配0个，1个，2个….k个，fun(i, j)的求解就可以转化为求解一系列的fun(i + k, j + 1)的值。
递归的出口：
当p已经没了，但是s还有，该情况无论如何也匹配不上了，返回false；
当p和s都没了 返回true；
当s没了p还有，该情况下只有p的后续全为’*’才能匹配上。
实现代码如下：
class Solution {
public boolean isMatch(String s, String p) {
return process(s.toCharArray(), p.toCharArray(), 0, 0);
}
public boolean process(char[] s, char[] p, int i, int j){
if(j == p.length){
return i == s.length;
}
if(i == s.length){
return p[j] == '*' && process(s, p, i, j + 1);
}
if(p[j] == '?' || p[j] == s[i]){
return process(s, p, i + 1, j + 1);
}
if(p[j] != '*'){
return false;
}
// p[j] == '*';
for(int k = 0; i + k <= s.length; k++){
if(process(s, p, i + k, j + 1)){
return true;
}
}
return false;
}
}动态规划
将上述递归解法改成动态规划，
定义dp 为(M + 1) * (N + 1)的布尔型数组，dp[i] [j] 为s从 i 开始，p从 j 开始能否匹配上，其中M为s的长度，N为p的长度。
转移函数：
baseline:
实现代码如下：
class Solution {
public boolean isMatch(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
int M = arrS.length;
int N = arrP.length;
// dp[i][j] s以i开头, p 以j开头能否匹配上
boolean[][] dp = new boolean[M + 1][N + 1];
dp[M][N] = true;
for(int j = N - 1; j >= 0; j--){
if(arrP[j] == '*'){
dp[M][j] = true;
}else{
break;
}
}
for(int i = M - 1; i >= 0; i--){
for(int j = N - 1; j >= 0; j--){
if(arrP[j] == '?' || arrS[i] == arrP[j]){
dp[i][j] = dp[i + 1][j + 1];
}else if(arrP[j] == '*'){
for(int k = 0; i + k <= M; k++){
if(dp[i + k][j + 1]){
dp[i][j] = true;
break;
}
}
}
}
}
return dp[0][0];
}
}该算法的时间复杂度为O（N* M ^2）。
优化后的DP
我们发现求解dp[i] [j]当p[j]为’*’时，需要从当前行（i行）开始对右边一列（dp[i] [j + 1] … dp[M] [j + 1]）进行或运算，我们发现dp[i + 1] [j]的求解也是从当前行（i + 1行）为从dp[i + 1 ] [j + 1] … dp[M] [j + 1]，因此优化后的转移函数如下：
实现代码如下：
public boolean isMatch(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
int M = arrS.length;
int N = arrP.length;
// dp[i][j] s以i开头, p 以j开头能否匹配上
boolean[][] dp = new boolean[M + 1][N + 1];
dp[M][N] = true;
for(int j = N - 1; j >= 0; j--){
if(arrP[j] == '*'){
dp[M][j] = true;
}else{
break;
}
}
for(int i = M - 1; i >= 0; i--){
for(int j = N - 1; j >= 0; j--){
if(arrP[j] == '?' || arrS[i] == arrP[j]){
dp[i][j] = dp[i + 1][j + 1];
}else if(arrP[j] == '*'){
dp[i][j] = dp[i + 1][j] || dp[i][j + 1];
}
}
}
return dp[0][0];
}时间复杂度为O（N * M）。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录