Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

正则表达式匹配

发表于 2020-04-11 | 分类于 算法题 | 0 | 阅读次数 146

题目:正则表达式匹配

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

  1. ' . '匹配任意单个字符
  2. ' * '匹配零个或多个前面的那个一个元素
例如 :
输入:
	s = "aaa" p = "a"  输出:false 解释:"a"无法匹配"aaa"整个字符串
	s = "aaa" p = "a*" 输出:true 
	s = "ab"  p = ".*" 输出:true
	s = "aab" p = "c*a*b" 输出:true
	s = "mississippi" p = "mis*is*p*." 输出:false

题解:

  1. 初始化一个长度为s.length()和p.length()的二维布尔数组match

  2. 将match[0][0]设置为true

  3. 初始化该数组中的值,当p中包含' * '时,当前位的值取决于该列前两位的值

    s\p(true)abc
    aF(此时的false为初始化时的值)FF
    *(match[0][2] = match[0][0],往下如果有*则同理)TFF
  4. 当前s中的字符与p中的字符匹配时,假设为match[ s -1 ][ p - 1 ],这个时候整个s是否能与p匹配取决于match[ s - 2 ][ p - 2 ]的值

    s\p(true)abc
    aTTF
    bTTF
    cFFF

    假设当前s字符为上方表格中的横向b,且p中字符也为竖列的b,那么此时,match数组的该值是否为true,取决于左上角a与a的匹配值。

题解代码如下:

class Solution {
    private boolean isMatch(String s, String p) {
        if (null == s || null == p) {
            return false;
        }
        if ("*".equals(p)) {
            return true;
        }
        int sLength = s.length();
        int pLength = p.length();
        boolean[][] match = new boolean[sLength + 1][pLength + 1];
        match[0][0] = true;
        for (int i = 1; i <= pLength; i++) {
            if (p.charAt(i - 1) == '*') {
                match[0][i] = match[0][i - 2];
            }
        }
        for (int si = 1; si <= sLength; si++) {
            for (int pi = 1; pi <= pLength; pi++) {
                if (p.charAt(pi - 1) == '.' || p.charAt(pi - 1) == s.charAt(si - 1)) {
                    // 单个字符匹配
                    // 此时,若匹配串中的上一个字符和正则串的上一个字符是可以匹配的
                    // 那么到当前为止,整个匹配串和正则串都是匹配的
                    match[si][pi] = match[si - 1][pi - 1];
                } else if (p.charAt(pi - 1) == '*') {
                    // 若当前正则串的该字符为*
                    if (p.charAt(pi - 2) == s.charAt(si - 1) || p.charAt(pi - 2) == '.') {
                        // 若此时匹配串中的该字符,与p中前一个字符可以匹配。
                        // 或者在该字符之前,s与p是匹配的,那么当前的字符也是可以匹配的
                        // 如,s=abcc,p=ab*
                        // 假设当前字符为s中的最后一位:c,且正则字符为*
                        // 那么在c之前,s如果与p是匹配的。则此时的c也是可以匹配的
                        match[si][pi] = match[si][pi - 2] || match[si - 1][pi];
                    } else {
                        match[si][pi] = match[si][pi - 2];
                    }
                }
            }
        }
        return match[sLength][pLength];
    }
}

关于另外的题解思路参考

# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
动态规划基础
Redis主从复制
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号