通配符匹配（动态规划）

题意

给一个字符串，和一个通配符表达式，问该字符串是否满足通配符表达式。

其中，通配符表达式除了字符外，只支持两种通配符

?匹配一个任意字符

*匹配任意个任意字符

思路分析

字符串相等比较

如果直接比较两个字符串相等，是按位比较

for(int i = 0;i < len;i++){
	if(s[i] != t[i])return false;
}
return true;

相邻字符关联关系

注意到 当发生字符串不匹配时，直接返回false

所以 要尝试匹配一个位置的字符串匹配的前提是，之前所有位置的已经完成匹配，也就是上一个位置是匹配成功的

用valid数组来记录对应位置匹配是否成功，有

for(int i = 0;i < len;i++){
	valid[i] = valid[i-1] && (s[i] == t[i]);
}

对于下标偏移量不同字符串匹配

当两个字符串匹配过程中，下标偏移不相同，则分别记录匹配位置的下标

valid[i][j] = valid[i-1][j-1] && (s[i] == t[j]);

写成if表达式

if(s[i] == t[j]){
	valid[i][j] = valid[i-1][j-1];
}

通配符?

因为?能匹配一个任意字符，所以不需要相等比较

if(s[i] == '?'){
	valid[i][j] = valid[i-1][j-1];
}

通配符*

如果匹配一个任意字符

if(s[i] == '*'){
	valid[i][j] = valid[i-1][j-1];
}

如果匹配0个任意字符，那么上次匹配的位置依然是上一个字符，但是没有消耗被匹配的字符串中的字符

if(s[i] == '*'){
	valid[i][j] = valid[i-1][j];
}

如果匹配>1个任意字符，那么上一次也是用*匹配的

if(s[i] == '*'){
	valid[i][j] = valid[i][j-1];
}

状态维持

上面所讲的都是状态转移

如果通配字符串前i个和字符串前j个有一种方案能匹配，则取这种方案即可

所以状态应该等于它原来的值或上新的值，而不是直接赋值

state = state | newstate

边界控制

因为空串也是一种字符串，所以状态设计为从0到字符串长度，一共字符串长度+1的大小

初始化，两个都是空串的时候，匹配成功valid[0][0] = true

题解

将上面的逻辑联系起来

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int lens = strlen(s); // string
        int lenp = strlen(p); // pattern
        vector<vector<bool>> valid(lenp+1,vector<bool>(lens+1, false)); // 状态
        valid[0][0] = true;
        for(int i = 0;i<lenp;i++){
            if(p[i] == '*'){ // 匹配空
                for(int j = 0;j<=lens;j++){
                    valid[i+1][j] = valid[i+1][j] | valid[i][j];
                }
            }
            for(int j = 0;j<lens;j++){
                if(s[j] == p[i] || p[i] == '?' || p[i] == '*'){ // 匹配一个
                    valid[i+1][j+1] = valid[i+1][j+1] | valid[i][j];
                }
                if(p[i] == '*'){ // 匹配 > 1 个
                    valid[i+1][j+1] = valid[i+1][j+1] | valid[i+1][j];
                }
            }
        }
        return valid[lenp][lens];
    }
};

复杂度分析

设两个字符串的长度分别为$mm$和$nn$

空间复杂度 : 状态为两个长度之积，$O(mn)O(mn)$

时间复杂度 : 所有状态计算一次$O(mn)O(mn)$