leetcode [10. 正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching/)

leetcode 10. 正则表达式匹配

给你一个字符串 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
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

  • 1 <= s.length <= 20

  • 1 <= p.length <= 30

  • s 只包含从 a-z 的小写字母。

  • p 只包含从 a-z 的小写字母,以及字符 .*

  • 保证每次出现字符 * 时,前面都匹配到有效的字符

Related Topics

递归

字符串

动态规划

思路1:动态规划

参考leetcode官方解释。s是主串,p是正则匹配串。

dp[i][j]表示s中前i个字符和p中前j个字符的匹配结果。(因为有*这个正则表达,所以需要每一个都匹配)。

匹配的字符总共有3种形式:

  • p[j]是字符,直接判断s[i] == p[j],如果成立,那么

    • dp[i][j] = dp[i-1][j-1]

  • p[j]是.,那么s[i] ==p[j]直接成立,

    • dp[i][j] = dp[i-1][j-1]

  • p[j]是*,因为可能会出现多个零个或者多个p[j-1]。所以这个地方需要分析。(需要注意:dp[i] [j]的含义就是s中前i个字符和p中前j个字符匹配。)

    • 匹配零次的情况:

      • 当s[i]!=p[j-1]时,可以把p[j-1]*忽略掉,只要s中前i个字符和p中前j-2个字符匹配成功,那么p[j-1]p[j]也就是p[j-1]*当做0次出现。举例:s=aaa,p=aaab* 匹配

        • dp[i][j] = dp[i][j-2]

      • 当s[i]==p[j-1]时,有可能s的前i个字符已经和p中前j-1个字符匹配,那么最后的p[j-1]*就是多余的。举例:s = aaa,b=aaaa*

        • dp[i][j] = dp[i][j-2]

      • 只要s中前i个字符和p中前j-2个字符匹配成功,那么P[j-1]*就是多余的,出现0次。

    • 当出现多次的情况:

      • 当s[i]==p[j-1]时,p[j-1]*至少出现一次以上,那么可以把s[i]忽略掉,继续向前判断s中前i-1个字符和p中前j个字符。

        • dp[i][j] = dp[i-1][j]

    经过以上分析,

    • 无论s[i]和P[j-1]是否相等,都可能出现0次的情况。dp[i][j] = dp[i][j-2]

    • 当s[i]==p[j-1]时,还可能出现匹配多次的情况。dp[i][j] = dp[i-1][j]

    • 无论哪一种情况出现,dp[i] [j]就为true。

边界分析:

举例:s = aa, p=a*,

  • s[1]=p[1],那么dp[1][1]=true

  • p[2]=*,那么s[1]=p[1] = dp[1][2] = dp[1][0] || dp[0][2]

  • 经过发现,我们还需要计算当s或者p为空串的情况。

    • 当s为空,p不为空,可能出现true的情况。举例:s=“”,p=a* 答案为true

    • 当s不为空,p为空,全部为false。

    • 当s为空,p为空,直接为true。

    • 所以需要特别计算当i=0的时候的dp[i] [j]。

class Solution {
​
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 0 ; i <= m;i++){
            for(int j = 1 ; j <= n;j++){
                //如果第j个字符是*
                if(p.charAt(j-1)=='*'){
                    //无论s第i个字符和p的第j-1个字符是否匹配成功,都可能出现0次情况
                    dp[i][j] = dp[i][j-2];
                    //如果s第i个字符和p的第j-1个字符匹配成功,可能出现多次情况(需要注意的是,第j-1个字符在s中的下标是i-2,这也是为什么在match中减一的原因)
                    if(match(s,p,i,j-1)){
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                }else if(match(s,p,i,j)){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
    //p[j]不是*的情况下 匹配s第i个和p中第j个 第i个字符的下标是i-1
    public boolean match(String s,String p,int i,int j){
        //因为p[j]!=*  当s为空串,p不为空串,一定为false
        if(i == 0){
            return false;
        }
        //任意匹配 直接成功
        if(p.charAt(j-1)=='.'){
            return true;
        }
        return s.charAt(i-1)==p.charAt(j-1);
    }
}
解答成功:
            执行耗时:2 ms,击败了68.96% 的Java用户
            内存消耗:39.7 MB,击败了31.39% 的Java用户
            

思路2:调用官方api

public boolean isMatch(String s, String p) {
    return s.matches(p);
}
解答成功:
            执行耗时:32 ms,击败了12.34% 的Java用户
            内存消耗:41.5 MB,击败了5.02% 的Java用户

调用官方api可能会匹配其他正则,时间消耗有点大。

上一篇:package.json


下一篇:openwrt web中文语言支持,并设置默认中文