LeetCode_动态规划_困难_10.正则表达式匹配

浅浅的花香味﹌ 2023-10-06 18:27 19阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**提示：**  
0 <= s.length <= 20  
0 <= p.length <= 30  
s 可能为空，且只包含从 a-z 的小写字母。  
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。  
保证每次出现字符 \* 时，前面都匹配到有效的字符

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/regular-expression-matching

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————动态规划（来自本题官方题解）
    class Solution {
        
    	public boolean isMatch(String s, String p) {
        
    	    int m = s.length();
    	    int n = p.length();
    	    // dp[i][j] == true 表示 s 的前 i 个字符与 p 中的前 j 个字符能够匹配
    	    boolean[][] dp = new boolean[m + 1][n + 1]; 
    	    // dp[0][0] 代表 s 和 p 均为空字符串，dp[1][1] 代表 s 和 p 的第一个字符(即在 s 和 p 中下标为 0 的字符)
    	    dp[0][0] = true;
    	    for (int i = 0; i <= m; i++) {
        
    	        for (int j = 1; j <= n; j++) {
        
    	            // p 的第 j 个字符为'*'
    	            if (p.charAt(j - 1) == '*') {
        
    	                //匹配 s 的第 i 个字符和 p 的第 j - 1 个字符
    	                if (match(s, p, i, j - 1)) {
        
    	                    // p 中 '*' 前面的字符在 s 中出现多次或者在 s 中只出现 1 次
    	                    dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
    	                } else {
        
    	                    // p 中 '*' 前面的在 s 中字符出现 0 次
    	                    dp[i][j] = dp[i][j - 2];
    	                }
    	            } else {
        
    	                // p 的第 j 个字符不为'*'
    	                //匹配 s 的第 i 个字符和 p 的第 j 个字符
    	                if (match(s, p, i, j)) {
        
    	                    //匹配成功，状态转移；匹配不成功，默认是 false
    	                    dp[i][j] = dp[i - 1][j - 1];
    	                }
    	            }
    	        }
    	    }
    	    return dp[m][n];
    	}
    	
    	//判断 x = s[i - 1] 和 y = p[j - 1] 这两个字符是否匹配，只有当 y 是 '.' 或者 x 和 y 本身相同时，这两个字符才会匹配
    	public boolean match(String s, String p, int i, int j) {
        
    	    //需要注意字符串中下标的变换
    	    if (i == 0) {
        
    	    	return false;
    	    }
    	    //'.':匹配任意单个字符
    	    if (p.charAt(j - 1) == '.') {
        
    	    	return true;
    	    }
    	    return s.charAt(i - 1) == p.charAt(j - 1);
    	}
    }

[Link 1]: https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/