本文主要是介绍JAVA练习49-正则表达式匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

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

示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

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

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

分析：

方法：动态规划+DFS

我们可以将 s 的长度设为 m ，p 的长度设为 n，那么字符串 s，p满足一下规律：

• 当 s[m] == p[n] 或者 p[n] == '.' 时，两个字符匹配成功，然后继续匹配 s[m-1]，p[n-1]。
• 当 p[n] == '*' 时，表示前一个字符出现 0 或 多次，所以继续匹配 s[m]，p[n-2] 和 s[m]，p[n-1]，如果 s[m] 和 p[n-1] 匹配成功，就继续匹配 s[m-1]，p[n-1] 和 s[m-1]，p[n-2]。

可以看出该题具有最优子结构，令 f (i, j) 为 s[i] 和 p[j] 匹配的结果，那么可以写出转移方程式：

f ( i, j ) = 

• true                                   i < 0 且 j < 0 时
• false                                 (i > 0 且 j < 0) 或 (i < 0 且 j > 0 且 p[ j-1 ] != '*')
• f (i - 1, j - 1)                      s[ i ] == p[ j ] 或 p[ j ] == '.' 时  ( i > 0 且 j > 0 )
• f (i, j - 2) || f (i, j - 1)          p[ j ] == '*' 时  ( i > 0 且 j > 0 )
• f (i - 1, j - 1) || f (i - 1, j)     (s[ i ] == p[ j ] 或 p[ j ] == '.') 且 (p[ j+1 ] == '*') 时  ( i > 0 且 j > 0 且 j+1 < p 的长度)

根据转移方程，因为考虑情况较多，我们可以利用深度优先递归（DFS）来实现，具体方式看代码。

时间复杂度：O(m*n)        m，n 分别为两个字符串的长度
空间复杂度：O(m*n)

class Solution {
    //定义两个字符串的字符列表
    char[] ss, ps;
    //字符串 p 的长度
    int len;

    public boolean isMatch(String s, String p) {
        ss = s.toCharArray();
        ps = p.toCharArray();
        len = ps.length;
        return dfs(ss.length - 1, ps.length - 1);
    }

    public boolean dfs(int i, int j){
        //都到头了
        if(i == -1 && j == -1){
            return true;
        }
        //正则表达式到头，被匹配字符串没到头
        if(j < 0){
            return false;
        }
        // '*' 表示 0 个和 1 个的情况
        if(ps[j] == '*' && (dfs(i, j-2) || dfs(i, j-1))){
            return true;
        }
        //被匹配字符串到头，正则没到头
        if(i < 0){
            return false;
        }
        //两个字符一样或正则为 '.'
        if(ss[i] == ps[j] || ps[j] == '.'){
            // '*' 表示多个情况
            if(j < len-1 && ps[j+1] == '*'){
                return dfs(i-1, j) || dfs(i-1, j-1);
            }
            return dfs(i-1, j-1);
        }
        return false;
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

这篇关于JAVA练习49-正则表达式匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！