动态规划学习——通符串匹配，正则表达式

目录

​编辑

一，通符串匹配

1.题目

2.题目接口

3，解题思路及其代码

二，正则表达

 1.题目

2.题目接口

3.解题思路及其代码

三，交错字符串

 1.题目

2，题目接口

3.解题思路及其代码

一，通符串匹配

1.题目

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

 

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示：

  • 0 <= s.length, p.length <= 2000
  • s 仅由小写英文字母组成
  • p 仅由小写英文字母、'?' 或 '*' 组成

2.题目接口

class Solution {
public:
    bool isMatch(string s, string p) {

    }
};

3，解题思路及其代码

在做动态规划问题时一般都是按照以下几步来走的：

1.确定状态转移方程

 像这种两个字符串的问题，一般都是定义二维的dp表按照两个字符串的第i和j下标位置来解决问题的。所以在这里定义dp[i][j]表示p在区间[1,j]中的字符是否存在能够匹配s在[1，i]中的字符。

2.状态转移方程

以s的第i个位置，p的第j个位置为研究对象来研究问题。此时分三种情况：1.s[i] == p[j]，或者p[j] == '?',在这种情况下dp[i][j] = dp[i-1][j-1]。

2.p[j] == "*"，在这种情况下就要看这个*可以顶替掉多少个s中的字符了：

顶替0个：dp[i][j] = dp[i][j-1]

顶替1个：dp[i][j] = dp[i-1][j-1]

顶替2个：dp[i][j] = dp[i-2][j-1]

顶替3个：dp[i][j] = dp[i-3][j-1]......

在以上i种情况下，我们只要找到一个为真便可以了。所以dp[i][j] = dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1].....。但是这样表示的话就需要遍历一遍，所以我们必须要优化以上状态表达，优化成为dp[i][j] = dp[i][j-1]||dp[i-1][j]。通过数学推导得知（将dp[i][j-1]后面的表达式转为一个状态表示）。

3.s[i]!=p[j]并且不是以上情况，在这种条件下dp[i][j]直接就是false。

3.初始化：

1.在字符串问题里，我们一般会在字符串的开头加上一个' '。

 2.因为*是可以匹配空的，所以当s字符串为空串时p为空串或者p全为*时也是可以匹配的。

初始化如下：

s = ' '+s;
p = ' '+p;

dp[0][0] = true;
//初始化：当我的s是一个空串时，我的p都是*
for(int i = 1;i<n+1;i++) if(dp[0][i-1]&&p[i] == '*') dp[0][i] = true;

4.填表顺序

根据状态转移方程很容易得出dp表的填写顺序是从左到右，从上到下。

5.返回值

 根据状态表示可知返回值是dp[m][n](m表示s的长度，n表示p的长度)    

代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        vector<vector<bool>>dp(m+1,vector<bool>(n+1));//dp[i][j]表示s,p分别以i,j结尾能不能完全匹配

        s = ' '+s;
        p = ' '+p;

        dp[0][0] = true;
        //初始化：当我的s是一个空串时，我的p都是*
        for(int i = 1;i<n+1;i++) if(dp[0][i-1]&&p[i] == '*') dp[0][i] = true;

        //以i,j为结尾研究问题

        for(int i = 1;i<m+1;i++)
        {
            for(int j = 1;j<n+1;j++)
            {
                //分两种情况
                if(p[j] == s[i]||p[j] == '?')
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j] == '*')
                {
                    //这颗*可以若干个字符，那可以配0个或者无数个得到的状态转移方程如下
                    //如果不匹配dp[i][j] = dp[i][j-1]
                    //如果匹配1个dp[i][j] = dp[i-1][j-1]
                    //如果匹配两个dp[i][j] = dp[i-2][j-1]
                    //.......
                    //在上面的情况中我们只要找到一种便可以
                    //dp[i][j] = dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]......

                    //优化：将上面的i个表达式变成n个表达式表示：dp[i][j] = dp[i][j-1]||dp[i-1][j]       
                     dp[i][j] = dp[i-1][j]||dp[i][j-1];
                    
                }

            }
        } 
        return dp[m][n];

    }
};

二，正则表达

 1.题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 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.题目接口

class Solution {
public:
    bool isMatch(string s, string p) {

    }
};

3.解题思路及其代码

但是这道题跟第一道题何其相似啊！！！'.'和'?'匹配规则是一样的，但是注意两个题目的'*'的匹配规则是是不一样的。所以在'*"和初始化处就要稍加改造了，改造如下：

初始化：

 for(int i = 2;i<n+1;i+=2) if(dp[0][i-2]&&p[i] == '*') dp[0][i] = true;

当遇到"*"时填表情况如下：

                else if(p[j] == '*')
                {
                    //按照题意在*前面一定有字符
                    if(p[j-1] == '.')//无敌匹配
                    {
                        dp[i][j] = dp[i][j-2]||dp[i-1][j];

                    }
                    else//不是.
                    {
                       //判断后再匹配
                       if(p[j-1] == s[i])
                       {
                           dp[i][j] = dp[i][j-2]||dp[i-1][j];
                       }
                       else
                       {
                           dp[i][j] = dp[i][j-2];
                       }
                    }

解题代码如下：

class Solution {
public:
    bool isMatch(string s, string p) {

        int m = s.size();
        int n = p.size();

        //经典加上空格
        s = ' '+s;
        p = ' '+p;



        //经典二维dp表
        vector<vector<bool>>dp(m+1,vector<bool>(n+1));

        dp[0][0] = true;

        //初始化:当s为空串时
        for(int i = 2;i<n+1;i+=2) if(dp[0][i-2]&&p[i] == '*') dp[0][i] = true;




        for(int i = 1;i<m+1;i++)
        {
            for(int j = 1;j<n+1;j++)
            {
                //分情况讨论
                if(p[j] == '.'||s[i] == p[j])
                {
                    //i,j位置匹配上了就得看dp[i-1][j-1]
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j] == '*')
                {
                    //按照题意在*前面一定有字符
                    if(p[j-1] == '.')//无敌匹配
                    {
                        dp[i][j] = dp[i][j-2]||dp[i-1][j];

                    }
                    else//不是.
                    {
                       //判断后再匹配
                       if(p[j-1] == s[i])
                       {
                           dp[i][j] = dp[i][j-2]||dp[i-1][j];
                       }
                       else
                       {
                           dp[i][j] = dp[i][j-2];
                       }
                    }
                }
            }
        }


           return dp[m][n];
    }
};

三，交错字符串

 1.题目

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

2，题目接口

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {

    }
};

3.解题思路及其代码

在看到三个字符串时，我就已经犯蒙了。感觉二维的dp表好像已经解决不了问题了，但是其实是可以解决问题的。解决步骤如下：

1，状态表示

仍然是开一个二维dp表dp[][]。仍然以s1的第i个位置和s2的第j个位置为研究对象研究问题。dp[i][j]表示s1的【1，i]区间和s2的【1，j】区间的字符能不能组成s3的【1，i+j】区间的字符。

2.状态转移方程

在这里我们也是分两种情况来讨论：

1，当s1[i] == s3[i+j]时，dp[i][j] = dp[i-1][j]。

2， 当s2[j] == s3[i+j]时，dp[i][j] = dp[i][j-1]。

3, 当以上两种情况都不成立的话，dp[i][j] = false。

所以dp[i][j] = (s1[i]==s3[i+j]&&dp[i-][j])&&(s2[j] == s3[i+j]&&dp[i][j-1])。

3，初始化

为了让下标对应所以得在每个字符的前面加上" "。

  //加上空格，因为空格有意义
   s1 = " "+s1;
   s2 = " "+s2;
   s3 = " "+s3;

当s1和s2都是空串时，能够组成空串

//初始化
dp[0][0] = true;

当有一个串为空时，另一个串要和s3一一匹配

      for(int i =1;i<m+1;i++)//代表s2为空串
        {
            if(s1[i] == s3[i])
            {
                dp[i][0] = true;
            }
            else 
            {
                break;
            }
        }

          for(int i =1;i<n+1;i++)//代表s1为空串
        {
            if(s2[i] == s3[i])
            {
                dp[0][i] = true;
            }
            else
            {
                break;
            }
        }

4，填表顺序

按照状态转移方程可知填表顺序为：从上到下，从左到右。

5，返回值

返回dp[m][n]

代码如下：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {

        int m = s1.size();
        int n = s2.size();
        if(m+n!=s3.size()) return false;

        //二维数组表示以i,j位置为结尾能够组成s3的i+j
        vector<vector<bool>>dp(m+1,vector<bool>(n+1));
         
         //加上空格，因为空格有意义
          s1 = " "+s1;
          s2 = " "+s2;
          s3 = " "+s3;

        //初始化
        dp[0][0] = true;

        for(int i =1;i<m+1;i++)//代表s2为空串
        {
            if(s1[i] == s3[i])
            {
                dp[i][0] = true;
            }
            else 
            {
                break;
            }
        }

          for(int i =1;i<n+1;i++)//代表s1为空串
        {
            if(s2[i] == s3[i])
            {
                dp[0][i] = true;
            }
            else
            {
                break;
            }
        }


        //经典以i,j位置为研究对象

        for(int i = 1;i<m+1;i++)
        {
            for(int j = 1;j<n+1;j++)
            {
               dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])
                 || (s2[j] == s3[i + j] && dp[i][j - 1]);
                
                
            }
        }

        return dp[m][n];

    }
};

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

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

相关文章

基于Python+WaveNet+MFCC+Tensorflow智能方言分类—深度学习算法应用（含全部工程源码）（三）

基于Python+WaveNet+MFCC+Tensorflow智能方言分类—深度学习算法应用（含全部工程源码）（三）

目录 前言引言总体设计系统整体结构图系统流程图 运行环境模块实现1. 数据预处理2. 模型构建1&#xff09;定义模型结构2&#xff09;优化损失函数 3. 模型训练及保存1&#xff09;模型训练2&#xff09;模型保存3&#xff09;映射保存 相关其它博客工程源代码下载其它资料下载…
阅读更多...
让植被管理更精准：数据可视化的新利器

让植被管理更精准：数据可视化的新利器

【小编整理了300可视化大屏源文件&#xff0c;需要可后台私~&#xff01;】 在当今时代&#xff0c;数据可视化技术已经成为了一个非常重要的技术。对于植被管理来说&#xff0c;数据可视化也有着非常重要的作用。通过将植被管理数据可视化&#xff0c;我们可以更加清晰地了解植…
阅读更多...
Apache Flink（十一）：Flink集群部署-Standalone集群部署

Apache Flink（十一）：Flink集群部署-Standalone集群部署

🏡 个人主页：IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主：加入大数据技术讨论群聊，获取更多大数据资料。 🔔 博主个人B栈地址：豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 目录 1. 节点划分
阅读更多...
SpringCloud-高级篇（七）

SpringCloud-高级篇（七）

前面在微服务里整合了Seata&#xff0c;下面利用Seata去解决分布式事务的问题&#xff0c;回去学习Seata中的四种解决方案 &#xff1a;首先学习XA模式 &#xff08;1&#xff09;XA模式 RM在前面讲的是资源管理器&#xff0c;在XA标准中RM都是由数据库来实现的&#xff0c;数…
阅读更多...
数据挖掘目标(Kaggle Titanic 生存测试)

数据挖掘目标(Kaggle Titanic 生存测试)

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns1.数据导入 In [2]: train_data pd.read_csv(r../老师文件/train.csv) test_data pd.read_csv(r../老师文件/test.csv) labels pd.read_csv(r../老师文件/label.csv)[Su…
阅读更多...
oracle详细安装教程（附带百度网盘资源）

oracle详细安装教程（附带百度网盘资源）

一,下载安装包途径 1.官网 Unauthorized Request 2.百度网盘分析 https://pan.baidu.com/s/1n221gdTK0Fcho839oRab9g 提取码1q2w 二&#xff0c;安装教程 1.下载完安装包后点击 setup.exe 如果出现一下的问题&#xff0c;使用windows10等系统安装oracle 11g等版本的数据库…
阅读更多...
二叉树的最大深度

二叉树的最大深度

问题描述&#xff1a; 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff1…
阅读更多...
ue4 解决角度万向锁的问题 蓝图节点

ue4 解决角度万向锁的问题 蓝图节点

问题&#xff1a;当角度值从359-1变化的时候&#xff0c;数值会经历358、357… 解决方法&#xff1a;勾上Shortest Path&#xff0c;角度值的会从359-1
阅读更多...
Ajax原理以及优缺点

Ajax原理以及优缺点

Ajax原理 1.Ajax的原理简单来说是在用户和服务器之间加了—个中间层(AJAX引擎)&#xff0c;通过XmlHttpRequest对象来向服务器发异步请求&#xff0c; 2.从服务器获得数据&#xff0c;然后用javascript来操作DOM而更新页面。使用户操作与服务器响应异步化。 3.这其中最关键的一…
阅读更多...
「Verilog学习笔记」简易秒表

「Verilog学习笔记」简易秒表

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 timescale 1ns/1nsmodule count_module(input clk,input rst_n,output reg [5:0]second,output reg [5:0]minute);always (posedge clk or negedge rst_n) begin if (~rst…
阅读更多...
Axure电商产品移动端交互原型，移动端高保真Axure原型图（RP源文件手机app界面UI设计模板）

Axure电商产品移动端交互原型，移动端高保真Axure原型图（RP源文件手机app界面UI设计模板）

本作品是一套 Axure8 高保真移动端电商APP产品原型模板&#xff0c;包含了用户中心、会员成长、优惠券、积分、互动社区、运营推广、内容推荐、商品展示、订单流程、订单管理、售后及服务等完整的电商体系功能架构和业务流程。 本模板由一百三十多个界面上千个交互元件及事件组…
阅读更多...
各地加速“双碳”落地，数字能源供应商怎么选？

各地加速“双碳”落地，数字能源供应商怎么选？

作者 | 曾响铃 文 | 响铃说 随着我国力争2030年前实现“碳达峰”、2060年前实现“碳中和”的“双碳”目标提出&#xff0c;为各地区、各行业的低碳转型和绿色可持续发展制定“倒计时”时间表&#xff0c;一场围绕“数字能源”、“智慧能源”、“新能源”等关键词的创新探索进…
阅读更多...
二百一十六、Flume——Flume拓扑结构之负载均衡和故障转移的开发案例（亲测，附截图）

二百一十六、Flume——Flume拓扑结构之负载均衡和故障转移的开发案例（亲测，附截图）

一、目的 对于Flume的负载均衡和故障转移拓扑结构&#xff0c;进行一个开发测试 二、负载均衡和故障转移 &#xff08;一&#xff09;结构含义 Flume支持使用将多个sink逻辑上分到一个sink组 &#xff08;二&#xff09;结构特征 sink组配合不同的SinkProcessor可以实现负…
阅读更多...
《地理信息系统原理》笔记/期末复习资料（10. 空间数据挖掘与空间决策支持系统）

《地理信息系统原理》笔记/期末复习资料（10. 空间数据挖掘与空间决策支持系统）

目录 10. 空间数据挖掘与空间决策支持系统 10.1. 空间数据挖掘 10.1.1. 空间数据挖掘的概念 10.1.2. 空间数据挖掘的方法与过程 10.1.3. 空间数据挖掘的应用 10.2. 空间决策支持系统 10.2.1. 空间决策支持系统的概念 10.2.2. 空间决策支持系统的结构 10.2.3. 空间决策…
阅读更多...
Onlyoffice本地部署超详细教程（附协作空间2.0新资讯）

Onlyoffice本地部署超详细教程（附协作空间2.0新资讯）

陈老老老板&#x1f934; &#x1f9d9;‍♂️本文专栏&#xff1a;生活&#xff08;主要讲一下自己生活相关的内容&#xff09;生活就像海洋,只有意志坚强的人,才能到达彼岸。 &#x1f9d9;‍♂️本文简述&#xff1a;ONLYOFFICE相信大家已经有所了解&#xff0c;本篇讲一下o…
阅读更多...
mjpg-streamer配置其它端口访问视频

mjpg-streamer配置其它端口访问视频

环境 树莓派4B ubuntu 20.04 U口摄像头 确认摄像头可访问 lsusb查看 在dev下可查看到video* sudo mplayer tv://可打开摄像头并访问到视频 下载mjpg-streamer并编译安装 在github下载zip包&#xff0c;下载的源码&#xff0c;需要编译安装 unzip解压 cd mjpg-streamer/mjp…
阅读更多...
聚观早报 |一加12首销；华为智能手表释放科技温暖

聚观早报 |一加12首销；华为智能手表释放科技温暖

【聚观365】12月12日消息 一加12首销 华为智能手表释放科技温暖 卡尔动力获地平线战略投资 英伟达希望在越南建立基地 努比亚Z60 Ultra影像规格揭晓 一加12首销 现在有最新消息&#xff0c;近日一加12该机已于昨日开售&#xff0c;售价4299元起。 外观方面&#xff0c;全…
阅读更多...
【Axure高保真原型】个性化自定义图片显示列表

【Axure高保真原型】个性化自定义图片显示列表

今天和大家分享个性化自定义图片显示列表的原型模板&#xff0c;鼠标点击多选按钮&#xff0c;可以切换按钮选中或者取消选中&#xff0c;按钮选中时&#xff0c;对应图片会在列表中显示&#xff0c;按钮取消后&#xff0c;对应图片会自动隐藏。那这个模板是用中继器制作的&…
阅读更多...
[C++] 模板进阶（非类型模板参数，特化，分离编译）

[C++] 模板进阶（非类型模板参数，特化，分离编译）

文章目录 1、非类型模板参数2、模板的特化2.1 什么是模板特化2.2 函数模板特化2.3 类模板的实例化2.3.1 全特化2.3.2 偏特化 3、模板分离编译3.1 什么是分离编译3.2 模板的分离编译3.3 解决方法 4、模板总结 1、非类型模板参数 模板参数分类类型形参与非类型形参。 类型形参即…
阅读更多...
flex布局，换行的元素上下设置间距

flex布局，换行的元素上下设置间距

要生成的效果图如下&#xff1a; display:flexflex-direction: row;flex-wrap: wrap;当我们使用弹性盒子布局后&#xff0c;默认元素是没有外边距的&#xff0c;紧挨着样式就有点丑&#xff0c;如果想使换行后&#xff0c;元素的外边距有个距离&#xff0c;可以用如下方法解决…
阅读更多...
最新文章

Copyright @ 2022~2023