二维动态规划解决正则表达式匹配问题

10.题目链接-来源：力扣（LeetCode）（困难）

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

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

示例 1：

输入：s = “aa” p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。

####思路：
本题是一道动态规划处理字符串的的经典题目。
对于’.’，一个简化的考虑就是，我们设计一个方法 match(char a, char b)，当且仅当 a = b 或者 a、b之中任意一个为’.’时返回 true 。
我们用 f(i, j)表示 s截至第i - 1个字符s[i - 1]的子串，与 p截至第j - 1个字符p[j - 1]的子串 是匹配的。那么我们要考虑的问题就是，f(i + 1, j)是否成立，f(i, j + 1)是否成立。
注意，f(0, n) 和 f(m, 0) 分别对应「s为空串」以及「p为空串」的情况，因此除了 f(0, 0) = true，其他的 0 行 0 列我们都要初始化为 false。
首先，对于p[j - 1] != ‘*‘的情况，我们有 f(i, j) = f(i - 1, j - 1) && match(s[i - 1], p[j - 1])
下面考虑p[j - 1] == ‘*‘ 的复杂情况。记住，我们考虑状态转移时保持 s 的指针[i - 1]不动，也就是说，我们先比较了f(i, j -2), f(i, j - 1), 之后才来到了 f(i, j)。

  • 此时，若p[j - 2] + ‘*‘视为无效串（即 p[j - 2]出现了0次），则 f(i, j) 回退到 f(i, j - 2) 的状态。
  • p[j - 2]已经出现过了，我们再让其多出现一次，看能否匹配，也就是我们要比较 mtach(s[i - 1], p[j - 2])，若成功，则 f(i, j) 的状态可以回退到 f(i - 1, j)。
    以上两种情况取并运算 ‘||’，即完成状态的转移。

时间复杂度：O(mn) n为 s 长度，m为 p 长度
空间复杂度：O(mn)

实现：

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
34
35
class Solution {
    public boolean isMatch(String s, String p) {
        int lens = s.length(), lenp = p.length();
        if (lenp == 0) {
            return lens == 0;
        }
        
        boolean dp[][] = new boolean[lens + 1][lenp + 1];
        
        dp[0][0] = true;
        
        for (int i = 0; i <= lens; i++) {
          for (int j = 1; j <= lenp; j++) {
              if (p.charAt(j - 1) != '*') {
                  if (i != 0 && match(s.charAt(i - 1), p.charAt(j - 1))) {
                      dp[i][j] = dp[i - 1][j - 1];
                  }
              } else {
                  dp[i][j] = dp[i][j - 2];
                  if (i != 0 && match(s.charAt(i - 1), p.charAt(j - 2))) {
                      dp[i][j] = dp[i - 1][j] || dp[i][j];
                  }
              }
          }
        }
        return dp[lens][lenp];
    }
    
    private boolean match(char s, char p) {
        if (p == '.' || s == '.') {
            return true;
        } 
        return s == p;
    }
}