您现在的位置是:首页 > 正文

剑指Offer JZ52 正则表达式匹配 C++实现

2024-04-01 01:47:57阅读 1

题目描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

解题思路


方法一:递归

1、思路:这题的解决思路主要在于如何根据' * '分情况讨论,比较字符串s和模式串p的第i位字符,分两种情况:

  • 当*(p+1)不等于' * '时,此时只需要比较*s和*p,当*s不为空且其等于*p或*p等于' . '时,当前字符匹配,继续递归匹配s+1和p+1,条件不满足的话说明匹配失败,*s为空的时候,此时*p还不为空,匹配也失败;
  • 当*(p+1)等于' * '时,此时*p可能重复出现0次或多次,当*s不为空且其等于*p或*p等于' . '时,递归匹配s+1和p(这时候就是判断*p重复出现多次的情况),直到s和p不匹配为止,此时*s为空或者*s不等于*p,回溯的时候需要递归匹配s和p+2,这时候就是判断*p重复出现0次的情况。

当字符串和模式串均为空,或者字符串不为空而模式串为空,递归终止,当模式串不为空,根据上述情况计算。

2、代码:

class Solution {
public:
    bool match(char* s, char* p)
    {
        //字符串和模式串均为空,匹配成功
        if (*s == '\0' && *p == '\0') return true;
        //字符串不为空,模式串为空,匹配失败
        if (*p == '\0') return false;
//------------模式串不为空的情况(字符串可能为空)---------------
        //模式串后一位不为'*'的情况
        if (*(p + 1) != '*') {
            if (*s != '\0' && (*s == *p || *p == '.')) {
                return match(s + 1, p + 1);
            } else {
                return false;
            }
        } else {
            bool flag = false;
            if (*s != '\0' && (*s == *p || *p == '.')) {
                flag = match(s + 1, p);
            }
            //返回值隐含了字符重复出现任意次(包括0次)的情况
            return flag || match(s, p + 2);
        }
    }
};

3、复杂度:

时间复杂度:O( );

空间复杂度:O( )。


方法二:动态规划

1、思路:开一个二维数组f[n][m]表示字符串s的前n位与模式串p的前m位是否匹配。从后往前推,如果只关注模式串p的最后一位p[m-1],思路就会清晰很多,分三种情况:

  • p[m-1]为普通字符,此时若s[n-1] = p[m-1],说明当前字符匹配,f[n][m]的匹配情况由f[n-1][m-1]决定,即f[n][m] = f[n-1][m-1],否则不匹配;
  • p[m-1]为' . ',它能匹配任意字符,情况同上,f[n][m] = f[n-1][m-1];
  • p[m-1]为' * ',此时说明p[m-2]可能重复0次或多次,当s[n-1] != p[m-2],必然重复0次,当s[n-1] = p[m-2]或者p[m-2] = ' . ',可能重复0次或多次,因此重复0次的情况可以先合并,重复0次就是跳过这两个字符,f[n][m]的匹配情况由f[n][m-2]决定,即f[n][m] = f[n][m-2];剩下的就是s[n-1] = p[m-2]或者p[m-2] = ' . '时p[m-2]重复多次的情况,此时f[n][m] = f[n-1][m],因为可能重复1次或多次,此时字符串s往前挪一位,模式串不变,继续看s[n-2]与p[m-2]是否匹配。

初始条件:f[0][0] = 1,即空串空正则匹配,f[1...n][0] = 0,即非空串空正则不匹配,然后就可以自底向上计算。

2、代码:

class Solution {
public:
    bool match(char* s, char* p)
    {
        int ns = strlen(s), np = strlen(p);
        vector<vector<int> > res(ns + 1, vector<int>(np + 1, 0));
        for (int i = 0; i <= ns; i++) {
            for (int j = 0; j <= np; j++) {
                if (j == 0) {
                    res[i][j] = (i==0) ? 1 : 0;
                } else {
                    if (p[j - 1] != '*') {
                        if (i >= 1 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) {
                            res[i][j] = res[i - 1][j - 1];
                        }
                    } else {
                        if (j >= 2) {
                            res[i][j] += res[i][j - 2];
                            if (i >= 1 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) {
                                res[i][j] += res[i - 1][j];
                            }
                        }
                    }
                }
            }
        }
        return res[ns][np];
    }
};

3、复杂度:

时间复杂度:O(nm);

空间复杂度:O(nm)。

网站文章

  • asp.net中运用百度地图api获取客户端的经纬度的方法

    asp.net中运用百度地图api获取客户端的经纬度的方法

    使用到的百度地图api接口需要自己申请成为开发者,点击百度地图开放平台进去注册。在asp.net中:前台页面代码:<!doctype html><html><head runat="server"> <meta charset="utf-8" /> <meta http-equiv="X-UA-Compatible" ...

    2024-04-01 01:47:31
  • ubuntu16.04离线安装mysql5.7.33

    由于一些原因,服务器不能联网,只能在一台能联网的机子上面下载相关软件,再将这台机子和服务器连接到一个局域网内,然后将下载好的软件传到服务器上。 有的软件可以很方便地安装。比如node和npm,但在安装...

    2024-04-01 01:47:24
  • session和cookie的区别

    session和cookie的区别

    cookie和session的区别

    2024-04-01 01:47:17
  • javaweb超级简单网上购物商城系统源码SSM框架结构

    javaweb超级简单网上购物商城系统源码SSM框架结构

    javaweb线上网上购物商城系统,采用ssm框架设计

    2024-04-01 01:46:51
  • 机器学习——实践

    机器学习——实践

    比如风控或者入侵检测,这两类任务都具有严重的数据不平衡问题,可以在算法学习的时候,为少类样本设置更高的学习权重,从而让算法更加专注于少类样本的分类情况,提高对少类样本分类的查全率,但是也会将很多多类样...

    2024-04-01 01:46:46
  • 配置中心ETCD搭建与简单使用 热门推荐

    1 ETCD配置 1.1 Ubuntu安装ETCD 以下配置均在Ubuntu16.04系统中。 (1)使用wget命令对ETCD进行安装 wget https://github.com/etcd-io...

    2024-04-01 01:46:38
  • QT connect使用简单介绍 最新发布

    QT connect使用简单介绍 最新发布

    QT connect 使用简单介绍

    2024-04-01 01:46:31
  • 吃豆人html代码原理,如何用HTML做一个吃豆人?

    吃豆人html代码原理,如何用HTML做一个吃豆人?

    首先做一个项目的先想如何去实现它。比如做一个吃豆人,如图:167b84dcbf0d3ed647b6b8c4abd75f92.jpg首先,需要分析这个吃豆人的组成部分。上半部分嘴,下半部分嘴,豆基本就三...

    2024-04-01 01:46:06
  • linux命令行设置颜色

    linux命令行设置颜色

    最近一直用linux,看着命令行一成不变的颜色,真的无语!话不多说,直接上教程。 1、编辑.bashrc文件. vim .bashrc 2、在.bashrc文件最后一行加入以下设置。(vim编辑器输入...

    2024-04-01 01:45:51
  • element--Cascader 点击文字选中+选中隐藏+多选

    //element Cascader 点击文字选中+选中隐藏+多选.el-cascader-panel .el-radio {width: 100%;height: 100%;z-index: 10;...

    2024-04-01 01:45:44