题解 | #字符串通配符#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 判断字符是否是字母或数字 */
static int check_lon(char ch)
{
    if(ch >= '0' && ch <= '9')
    {
        return 1;
    }
    else if((ch >= 'a' && ch <= 'z')
           || (ch >= 'A' && ch <= 'Z'))
    {
        return 2;
    }
    else
    {
        return 0;
    }
}

static int dynamic_planning(char *pattern, char *str)
{
    if(!pattern || !str)
    {
        return -1;
    }
    int m = strlen(pattern);
    int n = strlen(str);
    int dp[m+1][n+1];
    memset(dp, 0, (m+1)*(n+1)*sizeof(int));
    dp[0][0] = 1;
    for(int i = 1; i <= m; i++)
    {
        char ch1 = pattern[i-1];
        dp[i][0] = dp[i-1][0] && (ch1 == '*');
        for(int j = 1; j <= n; j++)
        {
            char ch2 = str[j-1];
            if(ch1 == '*')
            {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            }
            else
            {
                if(check_lon(ch2) == 2)
                {
                    dp[i][j] = dp[i-1][j-1] && 
                        (ch1 == '?'
                         || ch1 == ch2
                        || (ch1 == ch2-('a'-'A'))
                        || (ch1 == ch2+('a'-'A'))
                        );
                }
                else if(check_lon(ch2) == 1)
                {
                    dp[i][j] = dp[i-1][j-1] &&
                        (ch1 == '?' || ch1 == ch2);
                }
                else if(check_lon(ch2) == 0)
                {
                    dp[i][j] = dp[i-1][j-1] && (ch1 == ch2);
                }
            }
        }
    }
    return dp[m][n];
}

int main()
{
    char pattern[100] = {0};
    char str[100] = {0};
    if(gets(pattern) && gets(str))
    {
        int ret = 0;
        ret = dynamic_planning(pattern, str);
        if(ret)
        {
            printf("true\n");
        }
        else
        {
            printf("false\n");
        }
    }
    return 0;
}