LintCode_192 Wildcard Matching_192. wildcard matching c语言-程序员宅基地

技术标签： LintCode

Implement wildcard pattern matching with support for '?' and'*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Have you met this question in a real interview?

Yes

Example

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: A boolean
     */
    bool isMatch(const char *s, const char *p) {
    // write your code here
       if (s == NULL || p == NULL) {
            return false;
        }
        
        int n = strlen(s);
        int m = strlen(p);
        int f[n + 1][m + 1];
        
        memset(f, false, sizeof(f));
        
        f[0][0] = true;
        for (int i = 1; i <= n; i++)
            f[i][0] = false;
        
        for (int i = 1; i <= m; i++)
            f[0][i] = f[0][i - 1] && p[i - 1] == '*';
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1];//f[i][j - 1]为matchduoge，f[i - 1][j]是一个也不match
                } else if (p[j - 1] == '?') {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
                }
            }
        } // for
        
        return f[n][m];
    
   }
    
};

本文链接：https://blog.csdn.net/qq_31552435/article/details/52162324

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

动手深度学习矩阵求导_向量变元是什么-程序员宅基地

文章浏览阅读442次。深度学习一部分矩阵求导知识的搬运总结_向量变元是什么

月薪已炒到15w？真心建议大家冲一冲数据新兴领域，人才缺口极大！-程序员宅基地

文章浏览阅读8次。近期，裁员的公司越来越多今天想和大家聊聊职场人的新出路。作为席卷全球的新概念ESG已然成为当前各个行业关注的最热风口目前，国内官方发布了一项ESG新证书含金量五颗星、中文ESG证书、完整ESG考试体系、名师主讲...而ESG又是与人力资源直接相关甚至在行业圈内成为大佬们的热门话题...当前行业下行，裁员的公司也越来越多大家还是冲一冲这个新兴领域01 ESG为什么重要？在双碳的大背景下，ESG已然成...

对比传统运营模式，为什么越拉越多的企业选择上云？_系统上云的前后对比-程序员宅基地

文章浏览阅读356次。云计算快速渗透到众多的行业，使中小企业受益于技术变革。最近微软SMB的一项研究发现，到今年年底，78％的中小企业将以某种方式使用云。企业希望投入少、收益高，来取得更大的发展机会。云计算将中小企业信息化的成本大幅降低，它们不必再建本地互联网基础设施，节省时间和资金，降低了企业经营风险。科技创新已成时代的潮流，中小企业上云是创新前提。云平台稳定、安全、便捷的IT环境，提升企业经营效率的同时，也为企业..._系统上云的前后对比

esxi网卡直通后虚拟机无网_esxi虚拟机无法联网-程序员宅基地

文章浏览阅读899次。出现选网卡的时候无法选中，这里应该是一个bug。3.保存退出，重启虚拟机即可。1.先随便选择一个网卡。2.勾先取消再重新勾选。_esxi虚拟机无法联网

thinkpad E580解决ubuntu下不能连接wifi的问题_e580断开充电器后wifi无法连接-程序员宅基地

文章浏览阅读1.7k次。参考链接：https://blog.csdn.net/fljhm/article/details/79281655一开始以为是内核的问题，所以一直在升级内核，thinkpad采用的是rtl的网卡，所以我的网卡一直没有加载出来，跟博客的问题很像，采用了很多方法的都没有解决好，期间遇到/boot的内存不足的问题，想升级到18.04是有点困难，解决好这个问题可以愉快的使用linux了。..._e580断开充电器后wifi无法连接

Java面试题系列——JavaSE面试题（集合二）_javase 面试题-程序员宅基地

文章浏览阅读3.8k次。Java面试题系列——JavaSE面试题（集合二）_javase 面试题