问题描述

问题分析

分析题目，可以发现正则匹配每进一位的状态都是由前一个状态来决定的，所有我们可以用动态规划或者有穷自动机来求解。

---

第一种解法：动态规划

使用动态规划求解时，分析状态及变更情况，可知动态方程dp[ i ][ j ]中的 i 为被匹配字符串的下标，j 为匹配模式字符串的下标。动态方程如下：

1. if(p[j-1] == ‘*’)，
   1.1 dp[i][j] = dp[i][j-2] // *匹配到了0个前面的元素，此时的状态和p下标回退两个字符的状态一样。
   1.2 if(p[j-2] == s[i-1] || p[j-2]==’.’)，dp[i][j] = dp[i-1][j] // *匹配到了1个或多个前面的元素，此时的状态和s下标回退1个字符的状态一样。
2. if(p[j-1] != ‘*’),
   2.1 if(p[j-1] == s[i-1])，dp[i][j] = dp[i-1][j-1] //匹配成功，此时的状态和p下标回退1个字符、同时s下标回退一个字符的状态一样。
   2.2 if(p[j-1] == ‘.’)，dp[i][j] = dp[i-1][j-1] //匹配成功，此时的状态和p下标回退1个字符、同时s下标回退一个字符的状态一样。

• 时间复杂度：O( m*n) )，其中m和n 分别表示s和p的长度。
• 空间复杂度：O( m*n) )， dp[m+1][n+1]的容量大小。

Java代码

class Solution {
    public boolean isMatch(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();

        boolean[][] dp = new boolean[s_len+1][p_len+1];

        dp[0][0] = true;

        for (int i = 0; i < s_len+1; i++) {
            for (int j = 1; j < p_len+1; j++) {
                if (p.charAt(j-1) == '*'){
                    dp[i][j] = dp[i][j - 2] || (i > 0 && dp[i - 1][j] && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'));
                }else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.');
                }
            }
        }

        return dp[s_len][p_len];
    }
}

结果分析

以上代码的执行结果：

执行时间	内存消耗
8ms	34.9MB

---

第二种解法：动态规划（优化）

观察到当前状态仅和相邻层的状态相关，于是我们可以只用两行来存储状态，空间复杂度降低到了O( n )

Java代码

class Solution {
    public boolean isMatch(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();

        boolean[] result = new boolean[p_len+1];
        boolean[] cur = new boolean[p_len+1];
        cur[0] = true;

        for (int i = 0; i < s_len+1; i++) {
            for (int j = 1; j < p_len+1; j++) {
                if (p.charAt(j-1) == '*'){
                    cur[j] = cur[j - 2] || (i > 0 && result[j] && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'));
                }else {
                    cur[j] = i > 0 && result[j - 1] && (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.');
                }
            }
            result = cur;
            cur = new boolean[p_len+1];
        }
        return result[p_len];
    }
}

结果分析

以上代码的执行结果：

执行时间	内存消耗
7ms	34.6MB