leetcode 44. Wildcard Matching

最新推荐文章于 2024-02-23 11:05:25 发布

Coding_Reading

最新推荐文章于 2024-02-23 11:05:25 发布

阅读量331

点赞数

分类专栏： C++ 字符串文章标签：动态规划 leetcode

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/77839998

版权

C++ 同时被 2 个专栏收录

17 篇文章

订阅专栏

字符串

8 篇文章

订阅专栏

难度：hard

题目：

这里写图片描述

与leetcode10. Regular Expression Matching此题类似，同样采用动态规划，这两题解法很精彩，比较经典

AC解：

class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.length();
        int plen = p.length();

        if (slen == 0 && plen == 0)
            return true;
        vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false));
        //初始化数组
        dp[0][0] = true;
        for (int i = 0; i < plen && p[i] == '*'; i++)
            dp[0][i + 1] = true;

        for (int i = 1; i < slen + 1; i++)
            for (int j = 1; j < plen + 1; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
                    dp[i][j] = dp[i - 1][j - 1];

                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        return dp[slen][plen];
    }
};