首页 > 其他分享 >牛客BM76(正则表达式匹配)

牛客BM76(正则表达式匹配)

时间:2022-10-25 16:47:11浏览次数:100  
标签:字符 pp 匹配 ss 正则表达式 BM76 牛客 && dp

BM76 正则表达式匹配

具体实现:

1.确定dp数组以及下标的含义

dp[i][j]代表s中以i结尾的子串和p中j为结尾的子串是否匹配

2.状态转移

(1)p[j]为普通字符:匹配的条件是前面的字符匹配,同时 s 中的第 i 个字符和 p 中的第 j 位相同。

即 dp[i][j] = dp[i - 1][ j - 1] && s[i] == p[j] 。

(2)p[j]为'.':匹配的条件是前面的字符匹配,s 中的第 i 个字符可以是任意字符。

 即 dp[i][j] = dp[i - 1][ j - 1] && p[j] == '.' 。

(3)p[j]为‘*’:假设p[j - 1]的字符为a,然后根据a*十几匹配s中a的个数是0个、1个、2个。。。。

3.1 当匹配为0个:dp[i][j] = dp[i][j - 2]

3.2 当匹配为1个:dp[i][j] = dp[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')

3.3 当匹配为2个:dp[i][j] = dp[i - 2][j - 2] && ((s[i] == p[j - 1] && s[i - 1] == p[j - 1]) || p[j - 1] == '.')

表达式展开:

dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] && (s[i] 匹配 p[j - 1]) || dp[i - 2][j - 2] && ((s[i], s[i - 1] 匹配 p[j - 1])  || ........

i = i - 1代入

dp[i - 1][j] =              dp[i - 1][j - 2] || dp[i - 2][j - 2] && (s[i - 1] 匹配 p[j - 1]) || dp[i - 3][j - 2] && ((s[i - 1], s[i - 2] 匹配 p[j - 1])  || ........

dp[i - 1][j]从第二项开始每个item都比dp[i][j]相差了s[i]匹配p[j-1]

dp[i][j] = dp[i][j - 2](dp[i][j] 的第一项) || (dp[i - 1][j] && s[i]匹配p[j-1])

dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i]==p[j-1] || p[j-1] == '.'))

 

import java.util.*;
public class Solution {
    public boolean match (String ss, String pp) {
        // 技巧:往原字符头部插入空格,这样得到 char 数组是从 1 开始,而且可以使得 f[0][0] = true,可以将 true 这个结果滚动下去
        int n = ss.length(), m = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果下一个字符是 '*',则代表当前字符不能被单独使用,跳过
                if (j + 1 <= m && p[j + 1] == '*') continue;

                // 对应了 p[j] 为普通字符和 '.' 的两种情况
                if (i - 1 >= 0 && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }

                // 对应了 p[j] 为 '*' 的情况
                else if (p[j] == '*') {
                    f[i][j] = (j - 2 >= 0 && f[i][j - 2]) || (i - 1 >= 0 && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'));
                }
            }
        }
        return f[n][m];
    }
}

 

  • 时间复杂度:n 表示 s 的长度,m 表示 p 的长度,总共 n * mn∗m 个状态。复杂度为 O(n * m)O(n∗m)
  • 空间复杂度:使用了二维数组记录结果。复杂度为 O(n * m)O(n∗m)

标签:字符,pp,匹配,ss,正则表达式,BM76,牛客,&&,dp
From: https://www.cnblogs.com/zhaojiayu/p/16825370.html

相关文章

  • 正则表达式
    一、正则表达式    是用来描述字符串内容格式,使用它通常用于匹配一个字符串的内容是否符合格式要求。1.[]:表示一个字符,该字符可以是[]中指定的内容例如:[a......
  • JavaScript学习--正则表达式
       /[^0-9]/g表示除了0-9其他所有的更多在https://www.runoob.com/regexp/regexp-tutorial.html ......
  • 牛客SQL-牛客题:256-288(不干了)
    256.写一个sql查询,积分表里面出现三次以及三次以上的积分。若有多个符合条件的number,则按number升序排序输出SELECT`number`FROMgradeGROUPBY`number`HAVINGCOUN......
  • 正则表达式
    正则表达式(regularexpression)描述了一种字符串匹配的模式(pattern),可以用来检查一个串是否含有某种子串、将匹配的子串替换或者从某个串中取出符合某个条件的子串等。构......
  • Python正则表达式(Python RegEx)
    Python正则表达式目录Python正则表达式快速参考函数详解match()search()捕获和分组Match对象sub()compile()findall()finditer()split()参考博客与示例代码快速参考常用......
  • 【正则】578- 1小时真正掌握正则表达式
    1.基本匹配正则表达式其实就是在执行搜索时的格式,它由一些字母和数字组合而成.例如:一个正则表达式 ​​the​​​,它表示一个规则:由字母​​t​​​开始,接着是​......
  • day16 正则表达式 & 反射 & Java内存模型(JMM)
    day16class1)获取一个类的所有信息(变量、方法、构造方法)2)创建类对象newInstance()Field1)访问变量或给变量赋值Method1)执行具体类对象的指定方法3.Method(获取方法对......
  • day51-正则表达式02
    正则表达式025.4正则表达式语法025.4.6捕获分组详见5.3.3例子packageli.regexp;importjava.util.regex.Matcher;importjava.util.regex.Pattern;//演示分......
  • jsp页面中的正则表达式--主要用于js判断文本格式
    一、方括号[]举例:二、^三、元字符举例的话,就可以这么说,要实现要表示整数的话:[]就表示输入的文本框里面的数字的第一位,可以这么写--->[1-9]然后已知\d表示的与[0-9......
  • 正则表达式
    正则表达式正则表达式的概述正则表达式(RegularExpression)是一个描述字符模式的对象,用于对字符串进行匹配,一般用在有规律的字符串匹配中;常用于表单验证以及相关的......