leetcode力扣-10.正则表达式匹配解析【递归与动态规划】

leetcode力扣-10.正则表达式匹配解析【递归与动态规划】题目 给你一个字符串 s 和一个字符规律 p 请你来实现一个支持 和 的正则表达式匹配 匹配任意单个字符 匹配零个或多个前面的那一个元素 所谓匹配 是要涵盖 整个 字符串 s 的 而不是部分字符串 示例 1 输入 s aa p a

大家好,我是讯享网,很高兴认识大家。

题目

给你一个字符串 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
解释:"." 表示可匹配零个或多个(’’)任意字符(’.’)。
示例 4:
输入:s = “aab” p = “cab”
输出:true
解释:因为 '’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:s = “mississippi” p = "mis
isp."
输出:false
提示:
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符
---------------
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

递归

我们首先定义一个方法 m(String s, String p) 表示传入的字符串s与字符规律p是否匹配 ,返回 boolean

这道题目拿到手里,首先想到的就是递归。一步一步分析:

因为题目说了,s和p都是可能为空的,那么首先判断s和(或者)p为空的情况

说明:s-1 ,p-1 ,p-2 表示字符串截取掉末尾1位或者末尾2位

  1. 如果 s 和 p 都为空,则返回 true
  2. 如果 p 为空,则一定返回false,因为此时s不为空,始终无法匹配
  3. 如果 s 为空,并且p以*结尾(比如.*或者x*),m(s, p) = m(s, p-2) 此时相当于.*或者x*什么都没匹配,否则 m(s, p) = false

再考虑都不为空的情况:

递归算法
讯享网
还是需要简单说一下上面的方程是怎么得到的,对于s和p,如果存在s与p匹配的情况,那么

  1. 匹配0次,去掉p的末尾字符
  2. 匹配1次,去掉s的末尾字符 或者 同时去掉s/p的末尾字符(匹配1次就丢掉)

在p以*结尾时,为何没有同时去掉s/p的末尾字符呢?因为这个情况已经被包含了:

结果被包含不在需要另外写
代码实现

class Solution { 
    public boolean isMatch(String s, String p) { 
    int sLen = s.length(); int pLen = p.length(); if (s.equals(p)) { 
    return true; } if ("".equals(p)) { 
    return false; } if ("".equals(s)) { 
    if (p.endsWith("*")) { 
    return isMatch(s, p.substring(0, p.length() - 2)); } else return false; } if (p.endsWith("*")) { 
    if (p.charAt(pLen - 2) == '.') { 
    // 1. p跟s匹配 去掉s末尾 return isMatch(s.substring(0, sLen - 1), p) || // 2. p跟s匹配 去掉p末尾 isMatch(s, p.substring(0, pLen - 2)) ; } else if (p.charAt(pLen - 2) == s.charAt(sLen - 1)) { 
    // 1. p跟s匹配 去掉s末尾 return isMatch(s.substring(0, sLen - 1), p) || // 2. p跟s匹配 去掉p末尾 isMatch(s, p.substring(0, pLen - 2)) ; } else { 
    // 3. p跟s不匹配 去掉p末尾 return isMatch(s, p.substring(0, pLen - 2)); } } else if (p.endsWith(".")) { 
    // 4. 非*结尾匹配的情况 各自去掉末尾一位 return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1)); } else { 
    if (s.charAt(sLen - 1) == p.charAt(pLen - 1)) { 
    // 4. 非*结尾匹配的情况 各自去掉末尾一位 return isMatch(s.substring(0, sLen - 1), p.substring(0, pLen - 1)); } else return false; } } } 

讯享网

动态规划

动态规划三大特征

  1. 最优子结构 最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。后面阶段的状态可以通过前面阶段的状态推导出来。
  2. 无后效性 无后效性有两层含义,第一层含义是,在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步一步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。
  3. 重复子问题 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。

动态规划解题思路:

  1. 状态转移方程:状态转移方程法有点类似递归的解题思路。我们需要分析,某个问题如何通过子问题来递归求解,也就是所谓的最优子结构。根据最优子结构,写出递归公式,也就是所谓的状态转移方程。有了状态转移方程,代码实现就非常简单了。一般情况下,我们有两种代码实现方法,一种是递归加“备忘录”,另一种是迭代递推。
  2. 状态转移表:我们先画出一个状态表。状态表一般都是二维的,所以你可以把它想象成二维数组。其中,每个状态包含三个变量,行、列、数组值。我们根据决策的先后过程,从前往后,根据递推关系,分阶段填充状态表中的每个状态。最后,我们将这个递推填表的过程,翻译成代码,就是动态规划代码了。

本次解答过程,我们采用状态转移方程,因为方程比较好理解一些,而且画表格感觉有点麻烦。

我们需要定义一个二位数组存储s/p在不同索引位时,对应的匹配情况。比如boolean mem[sLen+1][pLen+1],维数为何不跟s/p的长度一致呢?因为s/p都是可能为空的,所以多出来的长度1其实是为了表示s/p为空的情况。

在这里插入图片描述
把上述的过程总结一下:

  1. p以*结果,a/b/c三种情况下:把f(i, j) = f(i, j-2)提取出来,然后再根据匹配的情况取 || f(i-1, j) 的结果
  2. 非*结尾,s与p末尾匹配,f(i,j) = f(i-1,j-1)
  3. 其他情况,无法匹配 f(i,j) = false;
  4. 理解s与p的匹配过程,是从后往前推导,而二维数组的赋值过程是从前往后的,因为后面的状态是依赖前面计算出来的结果的;

代码实现

讯享网class Solution { 
    public boolean isMatch(String s, String p) { 
    int sLen = s.length(); int pLen = p.length(); // 定义一个二维数组 存放各自位字符s与正则p相互匹配的结果 // 因为存在p或者(和)s为0的情况 所以二维数组的纬度比s/p的长度要多1 boolean[][] mem = new boolean[sLen + 1][pLen + 1]; // s和p都为0的情况 是可以匹配的 mem[0][0] = true; // 有个问题需要注意 // i/j并非是s/p的索引位 而需要减去1才是索引位 for (int i = 0; i <= sLen; i++) { 
    // 为何不让j=0呢,因为j=0的时候 必定是无法匹配的 for (int j = 1; j <= pLen; j++) { 
    if (p.charAt(j - 1) == '*') { 
    // 当 * 存在的时候 不论 * 前面的字符与s位字符是否匹配 // 计算方式的结果都是需要带上 如下表达式的 为什么呢 ? // 假如1. *前面是.或者*前面的字符与s的字符匹配 那么 // mem[i][j] = mem[i - 1][j] || mem[i][j - 2] ; // 假如2. *前面的字符与s的字符不匹配 那么 // mem[i][j] = mem[i][j - 2]; mem[i][j] = mem[i][j - 2]; // 为何是j - 1呢 ? 因为我需要判断的是 * 前面那一位 并且j - 1一定不会溢出(*前面一定有字符) if (matches(s, p, i, j - 1)) { 
    mem[i][j] = mem[i - 1][j] || mem[i][j]; } } else if (matches(s, p, i, j)) { 
    mem[i][j] = mem[i - 1][j - 1]; } } } return mem[sLen][pLen]; } private boolean matches(String s, String p, int i, int j) { 
    if (i == 0) { 
    return false; } if (p.charAt(j - 1) == '.') { 
    return true; } return s.charAt(i - 1) == p.charAt(j - 1); } } 
小讯
上一篇 2025-03-15 22:07
下一篇 2025-03-17 15:20

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76980.html