题解 | #字符串通配符#

思路：关于两个字符串匹配问题很容易想到用动态规划，首先定义dp[i][j]：字符串str前i个字符与字符串opt前j个字符的匹配结果：dp[i][j]=1表示匹配，dp[i][j]=0表示不匹配。初始化：dp[0][0]代表两个都为空，所以匹配故为1；第1行的其他元素明显为0；第一列的其他元素：如果str[0]=='*',dp[1][0]=1,后续要str[i]一直为'*'才会为1，否则为0。

递推公式：假设str='?*Bc*?'，opt='abcd'，为例

①如果str[i-1]==opt[j-1],或者str[i-1]=='?'，如果str[i-1][j-1]==1则str[i][j]=str[i-1][j-1]=1,如下表dp[1][1]

②如果s[i-1] ==''&&dp[i-1][j]==1；意味着此时''代表空字符，此时dp[i][j]=dp[i-1][j]=1，如dp[5][3],即 '?*BC*'与'abc'匹配。

③如果s[i-1] =='*'&&dp[i][j-1]==1；意味着此时'*'代表非空字符，此时dp[i][j]=dp[i][j-1]=1，如dp[2][3]，即'?*'与'abc'匹配。

注意事项：①字母不分大小写，所以上述递推①中相等判别处要加大小写情况；②通配符只能匹配字母和数字，所以上述递推①中通配符'?'处要增加字母和数字判别。

我的专栏牛客网刷题(C语言版)-华为机试

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main() {
    char str[101];//存储带有通配符的字符串
    char opt[101];//存储需匹配的字符串
    while (scanf("%s %s", str, opt) != EOF) {
        int i, j;
        /*dp数组定义
        dp[i][j]表示str中前i个元素与opt中前j个元素相匹配，1表示匹配，0表示不匹配。
        */
        int dp[strlen(str) + 1][strlen(opt) + 1]; //定义dp数组
        memset(dp, 0, sizeof(dp));//数组初始化全部为0
        /*dp数组初定义:
        ①dp[0][0]表示都没元素，则一定匹配为1
        ②第一列：str[1]=='*'如果dp[1][0]=='*'，则dp[i][0]==1
        ③第一行：显然除dp[0][0]均为0*/
        dp[0][0] = 1;
        for (i = 1; i < strlen(str) + 1; i++) {
            if (str[i - 1] == '*') //判断第一个字符是否为*
                dp[i][0] = dp[i - 1][0];
        }
        for (i = 1; i < strlen(str) + 1; i++) {
            for (j = 1; j < strlen(opt) + 1; j++) {
                if ((str[i - 1] == opt[j - 1] || str[i - 1] == opt[j - 1] + 32 ||
                        str[i - 1] == opt[j - 1] - 32) || (str[i - 1] == '?') && (isdigit(opt[j - 1]) ||
                                isalpha(opt[j - 1])))
                    dp[i][j] = dp[i - 1][j - 1];
                else if (str[i - 1] == '*')
                    dp[i][j] = (dp[i - 1][j] || dp[i][j - 1]);
            }
        }
        /*
        for(i=0;i<strlen(str)+1;i++){
            for(j=0;j<strlen(opt)+1;j++)
                printf("%d ",dp[i][j]);
            printf("\n");
        }*/
        if (dp[strlen(str)][strlen(opt)])
            printf("true\n");
        else
            printf("false\n");
    }

    return 0;
}