题解 | #通配符匹配#

通配符匹配

http://www.nowcoder.com/practice/e96f1a44d4e44d9ab6289ee080099322

class Solution {
public:
    /*
        其实一看到这个题目我首先想到的就是动摇规划
        那么就拿动态规划来说
        那么什么是变量
        dp[i][j]代表的是第s[0-i] p[0-j]是否匹配
        选择就是


    */

    bool isMatch(const char *s, const char *p) {
        int size_s = strlen(s);
        int size_p = strlen(p);
        if(size_s==0 && size_p==0) {
            return true;
        }
        if(size_s==0) {
            for(int i=0;i<size_p;i++) {
                if(p[i]!='*') {
                    return false;
                }
            }
            return true;
        }

        // 为了简化初始化
        vector<vector<bool>> dp(size_p+1,vector<bool>(size_s+1,false));
        dp[0][0]=true;

        for(int i=1;i<=size_p;i++) {
            if(p[i-1]!='*') {
                break;
            }
            if(p[i-1]=='*') {
                dp[i][0]=true;
            }
        }

        for(int i=1;i<=size_p;i++) {
            for(int j=1;j<=size_s;j++) {
                if(s[j-1]==p[i-1]) {
                    dp[i][j]=dp[i][j] || dp[i-1][j-1];
                } else if(p[i-1]=='?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if(p[i-1]=='*') {
                    dp[i][j]=dp[i][j] || dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];
                } else {
                    dp[i][j] = false;
                }

            }
        }

        for(auto a  : dp) {
            for(auto b : a) {
                cout<<b<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
        return dp[size_p][size_s];

    }
};
全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务