Leetcode算法系列| 10. 正则表达式匹配

目录

  • 1.题目
  • 2.题解
    • C# 解法一：分段匹配法
    • C# 解法二：回溯法
    • C# 解法三：动态规划

1.题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
1.‘.’ 匹配任意单个字符
2.‘.’ 匹配任意单个字符
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

  • 示例1:
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
  • 示例 2：
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
  • 示例3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
  • 提示：
    • 1 <= s.length <= 20
    • 1 <= p.length <= 20
    • s 只包含从 a-z 的小写字母。
    • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
    • 保证每次出现字符 * 时，前面都匹配到有效的字符

2.题解

  • 映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。
  • 第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。
  • 但是，如果反转后的数字大于 int.MAX\text{int.MAX}int.MAX，我们将遇到整数溢出问题。
  • 按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int\text{int}int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
    例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

C# 解法一：分段匹配法

  • 根据星号的位置将p切割为多个 尾星串 与 至多一个 无星串，然后从p头到p尾求M值。求解p的某段的M值时，需要根据上一段的M值来依次求解；若上一段M不包含任何值，则匹配失败。若p从头到尾走完了, 则判断最终的M中是否包含了 s.length-1 这个值， 若包含了，则s与p是匹配的。
public class Solution {
 public bool IsMatch(string s, string p)
       {
           List<int> M1 = new List<int>() { -1 };
           while (p.Length > 0 && M1.Count > 0)
           {
               List<int> M2 = new List<int>() { };
               int pStarIndex = p.IndexOf("*");
               foreach (int m1 in M1)
               {
                   string sRight = s.Substring(m1 + 1);
                   if (pStarIndex == -1)
                   {
                       var result = IsMatchNoStar(sRight, p);
                       //无星说明是p的最后一组，若匹配成功则s与p匹配，直接返回true；否则直接continue
                       if (result) return true;
                       continue;
                   }
                   //有星，需要 找到 p[0,starIndex] 与 s 的匹配点
                   //先判断p[0,starIndex-2]的字符与s的一一对应 
                   int mNow = -1;
                   bool isMatchBeforeStar = true;
                   for (int i = 0; i < pStarIndex - 1; i++)
                   {
                       if (i >= sRight.Length)
                       {
                           isMatchBeforeStar = false; break;
                       }
                       mNow = i;
                       if (!IsMatchChar(sRight[i], p[i]))
                       {
                           isMatchBeforeStar = false; break;
                       }
                   }
                   if (!isMatchBeforeStar) continue;
                   //因为*可以表示0个，所以先将mNow添加到 匹配点集
                   M2.Add(mNow + (m1 + 1));
                   mNow++;
                   //再看p[startIndex-1] 与 s的匹配点，找出所有的匹配点 
                   while (mNow < sRight.Length && IsMatchChar(sRight[mNow], p[pStarIndex - 1]))
                   {
                       M2.Add(mNow + (m1 + 1));
                       mNow++;
                   }
               }
               //将startIndex以及之前的串给舍弃，留下startIndex+1以及之后的串
               p = p.Substring(pStarIndex + 1);
               //更新M1 
               M1 = M2;
           }
           return M1.Contains(s.Length - 1);
       }

       public bool IsMatchNoStar(string s, string p)
       {
           if (s.Length != p.Length)
           {
               return false;
           }
           for (int i = 0; i < s.Length; i++)
           {
               if (!IsMatchChar(s[i], p[i]))
               {
                   return false;
               }
           }
           return true;
       }

       public bool IsMatchChar(char sc, char pc)
       {
           return ((pc == '.') || (sc == pc));
       }
}

可以牺牲部分可读性 来提高效率， 优化后的代码：

public class Solution {
      public bool IsMatch(string s, string p)
    {
        List<int> M1 = new List<int>() { -1 };
        List<int> M2 = new List<int>() { };
        int pStart = 0;
        while (p.Length - pStart > 0 && M1.Count > 0)
        {
            int pStarIndex = p.IndexOf("*", pStart);
            foreach (int m1 in M1)
            {
                int sStart = m1 + 1;
                int sRightLen = s.Length - sStart;
                if (pStarIndex == -1)
                {
                    //IsMatchNoStar
                    var result = true;
                    if (s.Length - sStart != p.Length - pStart) result = false;
                    else
                    {
                        for (int i = 0; i < s.Length - sStart; i++)
                        {
                            if (!((s[sStart + i] == p[pStart + i]) || (p[pStart + i] == '.')))
                            {
                                result = false;
                                break;
                            }
                        }
                    }
                    if (result) return true;
                    continue;
                }
                int mNow = -1;
                bool isMatchBeforeStar = true;
                int pLenBeforeStar = pStarIndex - pStart - 1;
                for (int i = 0; i < pLenBeforeStar; i++)
                {
                    if (i >= sRightLen)
                    {
                        isMatchBeforeStar = false; break;
                    }
                    mNow = i;
                    if (!((s[sStart + i] == p[pStart + i]) || (p[pStart + i] == '.')))
                    {
                        isMatchBeforeStar = false; break;
                    }
                }
                if (!isMatchBeforeStar) continue;
                M2.Add(sStart + mNow++);
                int pCharIndexBeforeStar = pStarIndex - 1;
                while (mNow < sRightLen && ((s[sStart + mNow] == p[pCharIndexBeforeStar]) || (p[pCharIndexBeforeStar] == '.')))
                    M2.Add(sStart + mNow++);
            }
            pStart = pStarIndex + 1;
            var tempMs = M1; M1 = M2; M2 = tempMs;
            M2.Clear();
        }
        return M1.Contains(s.Length - 1);
    }
}

1

  • 时间复杂度：O( pLen * sLen^2 )
    • 最坏的情况下，s全是同一个字母，p是同一个字母加星号，如 s=“aaaaaaa”,p= “aaa*” 。此时外层while以及找星的位置可以看作pLen,内层foreach每次都是对s的遍历，执行次数为sLen,再内层的 for与while加起来 又是对s的遍历，复杂度大概为 O( pLen * sLen^2 )
  • 空间复杂度：O( pLen * sLen )
    • 我第二层循环里面存在常数数量的变量定义，故为 O(pLen*sLen)

C# 解法二：回溯法

  • 回溯法解体的思路与分段匹配法类似，但使用递归后，只需要非常少的代码量。

  • 以p为主串，从左向右去匹配s，匹配成功的部分都去掉，也就是说 若最终s与p都变成了空串，则匹配成功。

  • 代码结构也很简单，首先是出口，然后是递归分支。

  • 出口EXIT：p变成空串时，若s也变成了空串，则匹配成功，否则匹配失败。

  • 分支A：p[1]为星号，直接去掉p的前两位，并递归。如 s=“b”,p=“a*b”.

  • 分支B：p[1]为星号时，若s第一位与p第一位匹配，去掉s第一位 , 并递归，如 “s=aab”,p=“ab"。否则匹配失败，如 s=“bba”,p="ab”.

  • 分支C：p[1]不为星号时，若s与p第一位匹配成功, 则都去掉第一位,并递归，如 s=“aab”,p=“aab*”. 否则匹配失败，如 s=“bab”, p=“aab*” .

  • 其中，当p[1]为星号时，分支A与分支B是【或】的关系，只要有一条成功，则匹配成功； 当p[1]不为星号时，就走C。

public class Solution {
   public bool IsMatch(string s, string p)
   {
       //出口，EXIT
       if (string.IsNullOrEmpty(p)) return string.IsNullOrEmpty(s); //Exit

        bool first_match = (   
           !string.IsNullOrEmpty(s) &&
           (p[0] == s[0] || p[0] == '.')
       );
      
       if (p.Length >= 2 && p[1] == '*')
           return (IsMatch(s, p.Substring(2)) ||       // A
                   (first_match && IsMatch(s.Substring(1), p))); //B
       else 
           return first_match && IsMatch(s.Substring(1), p.Substring(1)); // C
   }
}

可以使用下标指针来代替SubString，从而明显的提高代码效率。 优化后的代码：

public class Solution {
   public bool IsMatch(string s, string p) { return IsMatch1(s, 0, p, 0); }

   public bool IsMatch1(string s, int sStart, string p, int pStart)
   {
       if (pStart == p.Length) return sStart == s.Length; //Exit
       bool first_match = (
           sStart < s.Length &&
           (p[pStart] == s[sStart] || p[pStart] == '.')
       );
       if (p.Length - pStart >= 2 && p[pStart + 1] == '*')
           return (IsMatch1(s, sStart, p, pStart + 2) ||       // A
                   (first_match && IsMatch1(s, sStart + 1, p, pStart))); //B
       else
           return first_match && IsMatch1(s, sStart + 1, p, pStart + 1); // C
   }
}

2

  • 时间复杂度：O( (sLen+pLen) 2^(sLen+pLen/2) )*
  • 空间复杂度：O( (sLen+pLen) 2^(sLen+pLen/2) )*

C# 解法三：动态规划

public class Solution {
    public bool IsMatch(string s, string p)
    {
        bool[,] dp = new bool[s.Length + 1, p.Length + 1];
        dp[s.Length, p.Length] = true;
        for (int i = s.Length; i >= 0; i--)
        {
            for (int j = p.Length - 1; j >= 0; j--)
            {
                bool first_match = (i < s.Length && (p[j] == s[i] || p[j] == '.'));
                if (j + 1 < p.Length && p[j + 1] == '*')
                {
                    dp[i, j] = dp[i, j + 2]    //A
                        || first_match && dp[i + 1, j]; //B
                }
                else
                {
                    dp[i, j] = first_match && dp[i + 1, j + 1]; // C
                }
            }
        }
        return dp[0, 0];
    }
}

3

  • 时间复杂度：O(sLen*pLen)
    • 最table中每个值会被计算一次，不会重复计算，而每个格子的计算时间可认为是O(1),所以总时间复杂度为O(sLen*pLen)
  • 空间复杂度：O(sLen*pLen)
    • able空间复杂度为 O(sLen*pLen).

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/279625.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SimpleCG小游戏开发系列(2)--贪吃蛇

SimpleCG小游戏开发系列(2)--贪吃蛇

一、前言 在之前的C语言小游戏开发系列我们已经介绍了扫雷游戏的开发&#xff0c;本篇我们继续此系列第二篇&#xff0c;同样是比较简单但好玩的一个游戏--贪吃蛇。因为有了之前的游戏框架&#xff0c;我们只需要直接搬来原来的框架即可&#xff0c;可以省去不少活。 先看看游…
阅读更多...
布隆过滤器-使用原理和场景

布隆过滤器-使用原理和场景

一、概述 布隆过滤器&#xff08;Bloom Filter&#xff09;主要用来检索一个元素是否在一个集合中。它是一种数据结构bitMap,优点是高效的插入和查询&#xff0c;而且非常节省空间。缺点是存在误判率和删除困难。 二、应用场景 1、避免缓存穿透&#xff0c;当redis做缓…
阅读更多...
图像的颜色及Halcon颜色空间转换transfrom_rgb/trans_to_rgb/create_color_trans lut

图像的颜色及Halcon颜色空间转换transfrom_rgb/trans_to_rgb/create_color_trans lut

图像的颜色及Halcon颜色空间转换 文章目录 图像的颜色及Halcon颜色空间转换一. 图像的色彩空间1. RGB颜色 2. 灰度图像3. HSV/ HSI二. Bayer 图像三. 颜色空间的转换1. trans_from_rgb算子2. trans_to_rgb算子3. create_color_trans_lut算子 图像的颜色能真实地反映人眼所见的真…
阅读更多...
C++的面向对象学习(7)：面向对象编程的三大特性之：继承

C++的面向对象学习(7)：面向对象编程的三大特性之：继承

文章目录 前言一、继承&#xff1a;继承的类除了拥有上一级类的共性&#xff0c;也拥有自己的特性。二、继承方式&#xff1a;公有继承&#xff08;public inheritance&#xff09;、私有继承&#xff08;private inheritance&#xff09;和保护继承&#xff08;protected inhe…
阅读更多...
JavaScript基础知识点总结：从零开始学习JavaScript（六）

JavaScript基础知识点总结：从零开始学习JavaScript（六）

本章内容主要让小伙伴们自主练习 &#xff0c;建议大家先自己写出来答案&#xff0c;然后对照我的&#xff01;&#xff08;题不难主要培养自己的编程思维&#xff01;&#xff01;&#xff01;&#xff09; 如果大家感感兴趣也可以去看&#xff1a; &#x1f389;博客主页&…
阅读更多...
matlab导出高清图片，须经修改后放入latex（例如添加文字说明，matlab画图不易操作）

matlab导出高清图片，须经修改后放入latex（例如添加文字说明，matlab画图不易操作）

一、背景 我们在写文章时&#xff0c;使用matlab画图后&#xff0c;如果不需要对图片进行额外修改或调整&#xff0c;例如添加文字说明&#xff0c;即可直接从matlab导出eps格式图片&#xff0c;然后插入到latex使用。 通常latex添加图片&#xff0c;是需要eps格式的。 但很…
阅读更多...
两种汇编的实验

两种汇编的实验

week04 一、汇编-1二、汇编-2 一、汇编-1 1 通过输入gcc -S -o main.s main.c -m32 将下面c程序”week0401学号.c“编译成汇编代码 int g(int x){ return x3; } int f(int x){ int i 学号后两位&#xff1b; return g(x)i; } int main(void){ return f(8)1; } 2. 删除汇编代码…
阅读更多...
vr体验馆用什么软件计时计费，如遇到停电软件程序如何恢复时间

vr体验馆用什么软件计时计费，如遇到停电软件程序如何恢复时间

vr体验馆用什么软件计时计费&#xff0c;如遇到停电软件程序如何恢复时间 一、软件程序问答 如下图&#xff0c;软件以 佳易王vr体验馆计时计费软件V17.9为例说明 1、软件如何计时间&#xff1f; 点击相应编号的开始计时按钮即可 2、遇到停电再打开软件时间可以恢复吗&…
阅读更多...
跨域是什么，如何解决跨域

跨域是什么，如何解决跨域

文章目录 前言一、 什么是跨域&#xff1f;二、常见跨域问题三、如何解决跨域如何解决跨域&#xff08;方式&#xff09;前端解决跨域问题CORS反向代理JSONP 总结 前言 跨域是在开发中经常遇到的问题&#xff0c;那什么是跨域呢&#xff1f;及常见跨域的处理方案有哪些呢&…
阅读更多...
深入了解云原生：定义与特征解析

深入了解云原生：定义与特征解析

文章目录 一、云原生概述1.1 什么是云原生1.2 云原生组成要素1.3 补充资料 二、云原生的目标2.1 云原生关键目标2.2 云原生特性 三、云原生应用 VS 传统单体应用参考资料 一、云原生概述 1.1 什么是云原生 (1)云原生定义 云原生(Cloud Native) 是一种软件架构和开发方法论&a…
阅读更多...
D1671 75Ω视频放大驱动芯片 ，2.8~5.5V 应用于手持设备中 内 置 SAG端 子 6dB放 大 器 电 路

D1671 75Ω视频放大驱动芯片 ，2.8~5.5V 应用于手持设备中 内 置 SAG端 子 6dB放 大 器 电 路

D1671 是 一 块 带 4 级 低 通 滤 波 的 单 通 道 视 频 放 大 电 路 &#xff0c; 可 在 3V 或 5V的 低 电 压 下 工 作 。 该 电 路 用 在 有 TV 影 象 输 出 功 能 的 产 品 上 面 &#xff0c; 比 如 机 顶 盒 &#xff0c;监 控 摄 象 头 &#xff0c;DVD &#xff1b;此 …
阅读更多...
JSON 详解

JSON 详解

文章目录 JSON 的由来JSON 的基本语法JSON 的序列化简单使用stringify 方法之 replacerstringify 方法之 replacer 参数传入回调函数stringify 方法之 spacestringify 方法之 toJSONparse 方法之 reviver 利用 stringify 和 parse 实现深拷贝 json 相信大家一定耳熟能详&#x…
阅读更多...
WebGL以及wasm的介绍以及简单应用

WebGL以及wasm的介绍以及简单应用

简介 下面主要介绍了WebGL和wasm,是除了html,css,js以外Web标准所支持的另外两个大件 前者实现复杂的图形处理,后者提供高效的代码迁移以及代码执行效率 WebGL 简介 首先,浏览器里的游戏是怎么做到这种交互又显示不同的画面的? 试想用我们的前端三件套实现一下.好像可以…
阅读更多...
HackTheBox - Medium - Linux - Bagel

HackTheBox - Medium - Linux - Bagel

Bagel 今天我开始了《Red Team Development and Operations A Practical Guide》的学习&#xff0c;保持学习&#xff0c;后面差不多到时机后就学CRTOⅡ Bagel 是一款中等难度的 Linux 机器&#xff0c;其特点是电子商店容易受到路径遍历攻击&#xff0c;通过该攻击可以获取应…
阅读更多...
ZigBee协议栈 -- Zstack协议栈(Zstack2.5.1a)

ZigBee协议栈 -- Zstack协议栈(Zstack2.5.1a)

文章目录 Zstack 协议栈介绍ZStack 的安装ZStack 的结构系统初始化启动操作系统 设备的选择定位编译选项ZStack 中的寻址ZStack 中的路由OSAL 调度管理ZStack 中的串口通信设置配置信道配置 PANID 和要加入的网络最大有效载荷大小非易失性存储器 Zstack 协议栈介绍 CC2530 芯片…
阅读更多...
【华为机试】2023年真题B卷（python）-计算最大乘积

【华为机试】2023年真题B卷（python）-计算最大乘积

一、题目 题目描述&#xff1a; 给定一个元素类型为小写字符串的数组&#xff0c;请计算两个没有相同字符的元素长度乘积的最大值&#xff0c;如果没有符合条件的两个元素&#xff0c;返回0。 二、输入输出 输入描述: 输入为一个半角逗号分隔的小写字符串的数组&#xff0c;2 &…
阅读更多...
Collections

Collections

Collections Collections四种对集合进行排序的方式 方法名说明public static <T extends Comparable<? super T>> void sort (List<T> list)排序public static void reverse(List<?> list)逆序public static void shuffle(List<?> list)随机…
阅读更多...
使用element中el-cascader级联选择器实现省市区街道筛选(非动态加载)

使用element中el-cascader级联选择器实现省市区街道筛选(非动态加载)

<template><el-form ref"form" :model"form" label-width"80px"><el-form-item label"地址:" prop"addressList"><el-cascaderv-model"form.addressList":props"props":options&q…
阅读更多...
golang第一卷---go入门

golang第一卷---go入门

go入门 对于使用go的好处环境变量配置开发工具 参考网站 &#xff1a;go入门 对于使用go的好处 简单好记的关键词和语法。轻松上手&#xff0c;简单易学。更高的效率。比Java&#xff0c;C等拥有更高的编译速度&#xff0c;同时运行效率媲美C&#xff0c;同时开发效率非常高。…
阅读更多...
分布式技术之数据分布方式

分布式技术之数据分布方式

文章目录 数据分布设计原则数据分布方法哈希一致性哈希带有限负载的一致性哈希带虚拟节点的一致性哈希四种数据分布方法对比 在分布式系统中&#xff0c;具体是如何实现数据索引或数据分布的呢&#xff1f;目前最常用的方法就是哈希和一致性哈希。 数据分布设计原则 数据分布…
阅读更多...
最新文章

Copyright @ 2022~2023