通配符匹配（C++牛客网）

向右看齐 2023-01-13 00:47 114阅读 0赞

解题思路：

（1）递归（超时）

class Solution {
    public:
        bool helper(const char *s, const char *p) {
            if(*s=='\0' && *p=='\0') return true;
            else if(*s=='\0' && *p=='*') return helper(s,p+1);
            else if(*s=='\0') return false;
            
            if(*s!='\0' && *p=='\0') return false;
            else if(*s!='\0' && (*s==*p || *p=='?')) return helper(s+1,p+1);
            else if(*s!='\0' && *p=='*') return helper(s,p+1) || helper(s+1,p+1) || helper(s+1,p);
            else return false;
            
            return false;
        }
        
        bool isMatch(const char *s, const char *p) {
            return helper(s,p);
        }
    };

（2）动态规划

class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            int m=strlen(s),n=strlen(p);
            vector<vector<bool>> v(m+1,vector<bool>(n+1,false));
            v[0][0]=true;
            
            for(int i=1;i<n+1;i++) {
                if(p[i-1]=='*') v[0][i]=v[0][i-1];
            }
            
            for(int i=1;i<m+1;i++) {
                for(int j=1;j<n+1;j++) {
                    if(s[i-1]==p[j-1] || (p[j-1]=='?')) v[i][j]=v[i-1][j-1];
                    if(p[j-1]=='*') v[i][j]=v[i-1][j]||v[i][j-1]||v[i-1][j-1];
                }
            }
            return v[m][n];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客网刷题-括号匹配问题

前言：想要学好嵌入式，C语言与数据结构是必要熟练掌握的，而想熟练掌握一门语言，必须经过大量的练习，刷题，至少需要一两万行的代码量，才能具有一定的编程能力，至少拿到一个功能

亦凉/ 2024年04月06日 12:59/ 0 赞/ 45 阅读

相关通配符匹配（C++牛客网）

解题思路：（1）递归（超时） class Solution { public: bool helper(const char s, con

向右看齐/ 2023年01月13日 00:47/ 0 赞/ 115 阅读

相关等差数列（C++牛客网）

解题思路：（1）数学思想 include<iostream> using namespace std; int helper(

女爷i/ 2022年11月13日 10:29/ 0 赞/ 177 阅读

相关字符串通配符（C++牛客网）

解题思路：（1）使用递归 include<iostream> using namespace std; bool helper

怼烎@/ 2022年11月13日 00:46/ 0 赞/ 204 阅读

相关字符串排序（C++牛客网）

解题思路：（1）保存字母并排序（2）将非字母按顺序插入 include<iostream> include<cctype> include<u

矫情吗；*/ 2022年11月09日 12:58/ 0 赞/ 250 阅读

相关字符串字符匹配（C++牛客网）

解题思路：（1）map include<iostream> include<unordered_map> using namespace std;

比眉伴天荒/ 2022年10月22日 09:26/ 0 赞/ 187 阅读

相关合法IP（C++牛客网）

解题思路：（1）判断范围 include<iostream> include<vector> using namespace std;

￡神魔★判官ぃ/ 2022年10月22日 09:23/ 0 赞/ 196 阅读

相关牛客网

package myTest; import java.util.; public class Stacktest { public stat

川长思鸟来/ 2022年05月28日 12:22/ 0 赞/ 283 阅读

相关【牛客网】C/C++牛客网专项刷题（04）

以下为牛客网C/C++专项刷题： 1、有以下程序： include <stdio.h> include <string.h> voi

青旅半醒/ 2022年05月18日 04:49/ 0 赞/ 3241 阅读

相关牛客网——正则表达式匹配

题目描述请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而'' 表示它前面的字符可以出现任意次（包含0次）。

悠悠/ 2022年05月16日 15:29/ 0 赞/ 128 阅读