leetcode10 -- 正则表达式匹配

题目描述：

给你一个字符串 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 <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

解法：

首先理解题目的意思，要判断两个字符串s和p是否匹配，匹配返回true，否则返回false。

.可以代表任意单个字符

*可以代表零个或多个前面的元素

一、先考虑特殊情况

1.p和s均为空串，此时一定匹配。

2.p为空串，s不为空串，一定不匹配。

3.s为空串，但p不为空串，此时需要看p字符串末位是否为‘*’，如果是，则可以使得其左侧的字符出现零次，达到消除效果，如果情况正好可以消除完全，则可以匹配，否则不能匹配。

二、非空情况

这里是大问题包含子问题，要判断s与p是否匹配，那么就需要判断s与p的子串是否能匹配。

从左至右遍历s与p字符串，i表示s串遍历下标，j表示p串遍历下标，针对每个i和j，也就形成了s和p的不同子串。

我们可以s与p每个子串的末尾元素是否匹配，然后判断左侧剩余子串是否匹配。

用dp[i][j]表示s的前i个字符（s下标为0~i-1）与p的前j个字符（p下标为0~j-1）是否匹配，即如果dp[i][j]为true，s的前i个字符与p的前j个字符匹配，反之不匹配。

1.s[i-1]与p[j-1]匹配

那么如果s的第i个字符和p的第j个字符匹配的话，即当s[i-1]=p[j-1]（字符相等）或者p[j-1]='.'（.可以替代任意单个字符）时，两个串是否匹配则取决于除末尾位之外的剩余子串是否匹配，即s的前i-1个字符与p的前j-1个字符是否匹配，也就是dp[i][j]=dp[i-1][j-1]。

2.s[i-1]与p[j-1]不匹配

末位不匹配分两种情况：

1）末位字符不等且p[j-1]不是‘*’

这种情况没办法匹配了，能影响字符的只有‘.’和‘*’两个字符，但是*只会影响它左侧的元素，所以如果末位不等，没办法通过转变来使得其匹配。

2）末位字符不等但p[j-1]为‘*’

此时因为‘*’会影响左侧字符，所以需要分情况考虑。

（1）比较p[j-2]与s[i-1]是否匹配，如果匹配有以下几种情况：

p[j-1]为‘*’，那么p[j-2]在匹配过程中受到‘*’影响，出现的次数是不确定的，可能因为匹配而小时，也可能出现1次、2次甚至更多次，因为‘*’可以让其左侧元素出现不确定的数量，只要有某一种情况可以使剩余子串匹配则可行。

（2）如果p[j-2]与s[i-1]不匹配

此时p[j-1]='*'，可以使得p[j-2]出现零次而消失，那么就需要比较s[i-1]和p[j-3]是否匹配。

三、整体代码：

class Solution {
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
 
        // dp[i][j]，s的前i个字符与p的前j个字符是否匹配
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
 
        // s,p均为空
        dp[0][0] = true;
 
        // p空，s不空，false
        // s空，p不空，分情况（*影响)
        for (int j = 1; j <= cp.length; j++) {
            if (cp[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
 
        for (int i = 1; i <= cs.length; i++) {
            for (int j = 1; j <= cp.length; j++) {
                // 文本串和模式串末尾字符匹配
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp[j - 1] == '*') {
                    // p末尾是*
                    // p的*的前一个字符与s末尾能匹配
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }
}

参考题解：

https://leetcode.cn/problems/regular-expression-matching/solutions/