10. 正则表达式匹配/面试题19. 正则表达式匹配(困难)

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

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

示例 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

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

思路：

定义dp[ i] [j]为s的前i个元素是否可以被p的前j个元素所匹配

主要是分两种情况，一个是匹配‘.’和正常元素的，还有一种是匹配‘*’的

  1. 正常匹配：dp[i] [j] = dp[i-1] [j-1] &&(si与pj匹配判断)

  2. 匹配”*”：当p的第i个元素的下一个元素是星号 时会有两种情况：

    1. i元素需要出现0次，我们就保持s不变，将p的减掉两个元素，调用isMatch。例如s：bc、p：abc，我们就保持s不变，减掉p的”a“，调用isMatch(s:bc,p:bc)。
    2. i元素需要出现一次或更多次，先比较i元素和s首元素，相等则保持p不变，s减掉首元素，调用isMatch。例如s：aabb、p：abb，就保持p不变，减掉s的首元素，调用isMatch(s:abb,p:abb)。

    此时存在一些需要思考的情况，例如s：abb、p：a*abb，会用两种方式处理：

    1. 按照上述第二种情况比较i元素和s首元素，发现相等就会减掉s的首字符，调用isMatch(s:bb,p:a*abb)。在按照上述第一种情况减去p的两个元素，调用isMatch(s:bb,p:abb)，最终导致false。
    2. 直接按照上述第一种情况减去p的两个元素，调用isMatch(s:abb,p:abb)，最终导致true。

    作者：jerrymouse1998

    链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/javahui-su-dao-dong-tai-gui-hua-chao-xiang-xi-zhu-/

思路2：

回溯思路，未写

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean isMatch(String s, String p) {
        //dp[i][j]表示s的前i个字符是否可以被p的前j个字符所匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];//需要注意s和p都有可能取0
        dp[0][0]=true;//初始化，矩阵第一个肯定为真，s，p都为0，则一定匹配
        //dp[0][1]和第一列都为false不需要显式初始化
        //下面是第一行的情况,比较难想
        for(int k=2;k<=p.length();k++){
            //判断p的第二个字符是否为*，此时j元素需要0个，所以s不变，p减少两个字符
            dp[0][k]=p.charAt(k-1)=='*' && dp[0][k-2];//不好理解
        }
        //剩下的部分
        for(int i=0;i<s.length();i++){
            for(int j=0;j<p.length();j++){
                if(p.charAt(j)=='*'){//这个情况有点难
                    //两种情况:1.s不变[i+1],p移除两个元素[j+1-2]。
                    // 2.比较s的i元素和p的j-1(因为此时j元素为*)元素,相等则移除首元素[i+1-1],p不变。
                    dp[i+1][j+1]=dp[i+1][j-1] || (dp[i][j+1]&&isMatchhelper(s,p,i,j-1));
                }else{
                    //s的i元素和p的j元素是否相等,相等则移除s的i元素[i+1-1]和p的j元素[j+1-1]
                    dp[i+1][j+1]=dp[i][j]&&isMatchhelper(s,p,i,j);
                }
            }
        }
        return dp[s.length()][p.length()];
    }
    //判断s第i和p第j是否匹配
    public boolean isMatchhelper(String s,String p,int i,int j){
        return s.charAt(i)==p.charAt(j)||p.charAt(j)=='.';
    }
}