Leetcode 10. Regular Expression Matching解题思路分析

题目大意:

正则表达式匹配

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

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

匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *

示例 1:

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

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=10

解题思路分析:

这道题是比较典型要使用递归思想或者是动态规划DP来思考的题目。题目的难点也是关键点在于对星号的匹配。按照题目来分析,星号是不会单独出现,他需要根据前一个字符来匹配1个,多个或者0个连续相同字符。因此我们从星号的判断入手分析,分为两种情况,第一种情况,当前字符之后一位如果不是星号,那么只匹配s和p的当前位置即可,例如

String s = "abc";
String p = "a.b";
// 当index等于0时,匹配成功
s.charAt(0) = 'a';
p.charAt(0) = 'a';


// 当index等于1时,由于'.'可以匹配任何字符,同样匹配成功
s.charAt(1) = 'b';
p.charAt(1) = '.';

// 当index等于2时,匹配失败
s.charAt(2) = 'c';
p.charAt(2) = 'b';

另外一种情况即是p当前位之后一位的字符为星号的情况,这是本题的关键,我们知道,当前字符与之后一位的星号组合起来的长度是在0到无穷大的范围,如果长度为0,也就是说可以无视掉p当前字符以及星号,那么,匹配字符p的当前index可以跳到index + 2, 而s的index不变,问题就变成了判断p.charAt(index + 2)是否等于s.charAt(index)。反之,如果p的当前字符与星号的组合长度大于等于1,就要首先判断p的当前字符是否等于s的当前字符,并且再看p.charAt(index)是否等于s.charAt(index + 1)。我们用递归方法简单的描述一下上面的逻辑。

public boolean isMatch(String s, String p, int sIndex, int pindex) {
    char charP = p.charAt(pindex); // p当前字符
    char charS = s.charAt(sIndex); // s当前字符
    if (pindex + 1 < pLength && p.charAt(pindex + 1) == '*') {
        return (charS == charP || charP == '.') && isMatch(s, p, sIndex + 1, pindex) 
               || isMatch(s, p, sIndex, pindex + 2);
    } else {
       return (charS == charP || charP == '.') && isMatch(s, p, sIndex + 1, pindex + 1);
    }
}

当然,上面的代码只是一个简单的思路,并没有考虑charAt()方法越界的情况。在LeetCode提交之后顺利通过(AC),不过执行速度稍微有些缓慢,只击败了60%的代码执行效率。仔细一分析,才恍然大悟,说好的动态规划呢?我们需要一个数组来记录下,对应sIndex和pindex的匹配结果,这样可以避免不必要的重复计算,最后是完整的逻辑代码。

int pLength = 0;
int sLength = 0;
Boolean[][] dp;

public boolean isMatch(String s, String p) {
    pLength = p.length(); // 字符串p的长度
    sLength = s.length(); // 字符串s的长度
    dp = new Boolean[sLength + 1][pLength + 1]; // 保存中间计算结果的数组
    return isMatch(s, p, 0, 0); // 分别从s和p的第0位开始匹配
}

public boolean isMatch(String s, String p, int sIndex, int pindex) {
    // 如果匹配字符串p的当前位置已经超过最后一位(p已经消耗完)
    if (pindex >= pLength) {
        // 这时如果s还有剩余,那么一定无法完整匹配,返回false。反之则完全匹配
        return sIndex >= sLength;
    }
    // 如果对应的sIndex和pindex的计算结果不为空,直接返回该结果。
    if (dp[sIndex][pindex] != null) {
        return dp[sIndex][pindex];
    }
    // 当前pindex对应的字符
    char charP = p.charAt(pindex);
    // 当前sIndex对应的字符,注意越界。如果越界,charS定义为'-'
    char charS = (sIndex < sLength) ? s.charAt(sIndex) : '-';
    // p当前位的下一个字符为星号的情况
    if (pindex + 1 < pLength && p.charAt(pindex + 1) == '*') {
        // 1. s当前字符等于p当前字符,或者p当前字符为'.',递归比较pindex与sIndex + 1
        // 2. 忽略掉p的当前字符以及之后的星号,递归比较pindex + 2与sIndex
        // 上述两种情况一真则真
        dp[sIndex][pindex] = sIndex < sLength && (charS == charP || charP == '.')
                && isMatch(s, p, sIndex + 1, pindex) || isMatch(s, p, sIndex, pindex + 2);
        return dp[sIndex][pindex];
    } else {
        // p当前位的下一个字符不是星号的情况,
        // 比较当前位是否相同,并递归看下一位是否相同
        dp[sIndex][pindex] = sIndex < sLength && (charS == charP || charP == '.')
                && isMatch(s, p, sIndex + 1, pindex + 1);
        return dp[sIndex][pindex];
    }
}

其实LeetCode中还有一题与本题非常相似,同样可以利用此方法来思考,大家可以自己练习一下。题号 44. Wildcard Matching。同时这道题还有另外一种解法,有兴趣可以参考另外一篇文章:

leetcode 44. Wildcard Matching 解题思路分析

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-10-regular-expression-matching解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。