题解 | 字符串通配符

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

bool is_alnum(char c)
{
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'));
}

bool charMatch(char c1, char c2)
{
    return tolower(c1) == tolower(c2);
}

bool isMatch(const char *s, const char *p)
{
    int n = strlen(s);
    int m = strlen(p);
    bool dp[n + 1][m + 1];

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = false;
        }
    }

    dp[0][0] = true;

    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == '*')
        {
            dp[i][0] = dp[i - 1][0];
        }
        else
            break;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i - 1] == '?')
            {
                if (is_alnum(p[j - 1]))
                    dp[i][j] = dp[i - 1][j - 1];
            }
            else if (s[i - 1] == '*')
            {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
            else
            {
                if (charMatch(s[i - 1], p[j - 1]))
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }

    return dp[n][m];
}

int main()
{
    char s[110] = {0};
    char p[110] = {0};

    fgets(s, sizeof(s), stdin);
    fgets(p, sizeof(p), stdin);

    s[strcspn(s, "\n")] = '\0';
    p[strcspn(p, "\n")] = '\0';

    if (isMatch(s, p))
    {
        printf("true\n");
    }
    else
    {
        printf("false\n");
    }

    return 0;
}