剑指Offer（五十二）-- 正则表达式匹配（递归实现）

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

示例1输入

"aaa","a*a"

返回值

true

思路以及解答

这道题，仔细一想，感觉情况很多，很凌乱，此处介绍的是递归的做法，其实本题还可以使用动态规划。最重要的是需要分类讨论，原串定义为str,模式串为pattern。

• 如果pattern长度为0
  • 且str长度为0,说明刚刚好匹配完，返回ture
  • str长度不为0，说明没有匹配完，返回false
• 如果pattern的长度大于0
  • 分为两种情况讨论，一种是直接把*和*前面的字符去掉，相当于匹配了0个，然后接着比较；另外一种是，如果str的长度大于0，并且第一个字符匹配，那就把str的第一个字符去掉，两者接着匹配。
  • 如果pattern的长度大于1，且第2个字符是*，说明前面的字符可以匹配0，1或者多次
  • 否则，说明第二个字符不是*，那么就直接比较第一个字符是不是匹配，同时将后面的字符进行匹配。

注意：上面说的第一个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为'.'的情况。

    public boolean match(String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        // 第二个字符是'*'
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
            // 匹配0次，直接把'*'去掉，两者判断
            return match(str, pattern.substring(2))
                    // 第一个字符相同的时候，去掉第一个字符，判断后面的（相当于匹配多次）
                    || (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern);
        } else {
            // 第二个字符不是 '*'的时候，判断第1个字符是否相同，相同的时候再从第2位开始比较
            return str.length() > 0 
                    && firstSame(str, pattern) 
                    && (match(str.substring(1), pattern.substring(1)));
        }
    }

    // 判断第一个字符是不是相同
    private boolean firstSame(String s, String p) {
        // 两个相同，或者有一个是"."
        return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
    }

当然，这种做法不是最优的，使用了大量的递归操作，并且重复递归，时间复杂度比较高。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -