「动态规划学习心得」正则表达式匹配

正则表达式匹配

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

• ‘.’ 匹配任意单个字符
• ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

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

题目解析：

我们定义dp[i][j]表示s串前i个字符能否被p串前 j 个字符匹配

• 初始状态

  • dp[0][0] = true ，即两个都是空串，则肯定不匹配

  • 当 i > 0时，dp[i][0]= false，即s串是非空串，p串是空串，则肯定不能够匹配

  • 当 j >0时，dp[0][j] = dp[0][j-2]，即p串不是空的，但是s串是空的，此时想要匹配，必须利用p串中的*来匹配前面的字符0次使得当前p串为空串，才可能匹配

    比如：p串为"a*b*c*d*"

• 目标状态：显而易见最终的答案就是dp[n][m]，n和m分别为s串和p串的长度

• 中间状态转移：从右往左遍历「因为这样可以提前考虑匹配符号.和*」,对于dp[i][j]「最后两个字符下标分别是i-1和j-1」

  • 如果s[i-1] == p[j-1]，则当前两个字符匹配，如果前面的能够匹配，则dp[i][j]能够匹配，即：dp[i][j] = dp[i-1][j-1]
  • 如果s[i-1] != p[j-1]，我们需要先看下p[i-1]是什么，其只有三种可能：普通字符、*,.
    • 如果是普通字符，则直接匹配失败dp[i][j] = false「因为我们是从右往前考虑，前面的通配符影响不到当前字符」
    • 如果当前字符是.，则当前字符可以匹配，则需要看前面的是否能否匹配dp[i][j] = dp[i-1][j-1]
    • 如果当前字符是*，则要看p串其前面的字符「下标为 j-2 」是什么，看看前面的字符能否与s[i-1]匹配
      • 不匹配，即s[i-1] != p[j-2] && p[i-2] != '.'，那么当前*的作用肯定是匹配前面的字符「下标j-2」0次，然后看p[0 ~ j-3]能否和s0 ~ [i-1]匹配，即dp[i][j] = dp[i][j-2]
      • 匹配，即s[i-1] == p[j-2] || p[i-2] == '.'
        • 通过*重复p[j-2] 0次，则最终能否匹配取决于s[0_i-1]和p[0j-3]能否匹配，即dp[i][j] = dp[i][j-2]
        • 通过*重复p[i-2] 1次，则最终能否匹配取决于 s[0 ~ i-2]和p[0 ~ j-3]能否匹配，即dp[i][j] = dp[i-1][j-2]
        • 通过*重复p[i-2] 多次「2次及以上」，则最终能否匹配取决于 s[0~i-2]和p[0 ~j-1]能否匹配「因为是匹配多次，所有我们可以把当前这一次匹配去掉，但是要保留*,因为要进行多次匹配」，即dp[i][j] = dp[i-1][j]

中间状态转移比较复杂，情况分布图如下所示：

java版本：

class Solution {
    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;
        char [] ss = s.toCharArray();
        char [] ps = p.toCharArray();
        int n = s.length(), m = p.length();
        boolean [][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(ps[j-1] == ss[i-1] || ps[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(ps[j-1] == '*'){
                    if(ps[j-2] != ss[i-1] && ps[j-2] != '.'){
                        dp[i][j] = dp[i][j-2];
                    }else{
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }
                }
            }
        }
        return dp[n][m];
    }
}
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

golang版本：

func isMatch(s string, p string) bool {
    n,m := len(s),len(p)
    dp := make([][]bool,n+1)
    for i := 0;i <= n;i++{
        dp[i] = make([]bool,m+1)
    }
    // 初始状态初始化
    dp[0][0] = true
    for j := 2;j <= m;j++{
        if p[j-1] == '*'{
            dp[0][j] = dp[0][j-2]
        }
    }
    // 中间状态转移
    for i := 1;i <= n;i++{
        for j := 1;j <= m;j++{
            if s[i-1] == p[j-1] || p[j-1] == '.'{
                dp[i][j] = dp[i-1][j-1]
            }else{
                if p[j-1] >= 'a' && p[j-1] <= 'z'{
                    dp[i][j] = false
                }else if p[j-1] == '*'{ // 是*
                    if p[j-2] != s[i-1] && p[j-2] != '.'{
                        dp[i][j] = dp[i][j-2]
                    } else{
                        dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]
                    }
                }
            }
        }   
    }
    return dp[n][m]
}
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
32
33