题目

LeetCode.10.正则表达式匹配（困难）

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

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

题解

解法1：递归

题目已经给出了匹配规则。

怎么做匹配？

用两个指针i和j分别指向s和p的开头，一直匹配，如果两个指针都能到达s和p的末尾，说明匹配成功。

`*`的注意事项

p中遇到*时要考虑它前面一个字符是什么。

但我们是从左向右匹配的，所以在当前位置匹配字符时，要考虑p的下一个位置是不是*。

如何用`*`匹配多个字符？

可以匹配0个字符、1个字符，多个字符递归去解决。

匹配0个字符时，指针i不动，j跳到j + 2
匹配1个字符时，先要看s[i]是不是跟p[j]匹配，匹配的话j是不动的，因为可以匹配多个。

边界处理

按道理j == p.length && i == s.length时，说明匹配完成，否则没有完成匹配。
但是因为有*的存在，可能j还指向*前面一个字符，i会先到末尾，即此时j != p.length && i == s.length，也可能是匹配成功的，i发现s后面没有字符可匹配时，可以走*匹配0个字符的逻辑，这样j就到达末尾了。

递归解法

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val m = s.length
        val n = p.length
        fun match(i: Int, j: Int): Boolean {
            if (j == n) return i == m
            val isCharMatch = i < m && (s[i] == p[j] || p[j] == '.')
            val isStarPattern = j <= n - 2 && p[j + 1] == '*'
            return if (isStarPattern) {
                val isZeroMatched = match(i, j + 2)
                val isOneMatched = isCharMatch && match(i + 1, j)
                isZeroMatched || isOneMatched
            } else {
                isCharMatch && match(i + 1, j + 1)
            }
        }
        return match(0, 0)
    }
}

时间复杂度：平均O(n * 2 ^ 星号数)，最差O(2^n)，

解法2：记忆化递归

普通递归存在很多重叠子问题。

比如执行两次match(i + 1, j)再执行两次match(i, j + 2)的结果跟执行两次match(i + 1, j + 1)的结果是一样的。

所以需要记录中间结果。

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val m = s.length
        val n = p.length
        val memo = mutableMapOf<String, Boolean>()
        fun match(i: Int, j: Int): Boolean {
            if (j == n) return i == m
            val key = "$i,$j"
            if (memo.contains(key)) return memo[key]!!
            val isCharMatch = i < m && (s[i] == p[j] || p[j] == '.')
            val isStarPattern = j <= n - 2 && p[j + 1] == '*'
            val matched = if (isStarPattern) {
                val isZeroMatched = match(i, j + 2)
                val isOneMatched = isCharMatch && match(i + 1, j)
                isZeroMatched || isOneMatched
            } else {
                isCharMatch && match(i + 1, j + 1)
            }
            memo[key] = matched
            return matched
        }
        return match(0, 0)
    }
}

时间复杂度：平均O(n*(星号数+1))，最差O(n²)

解法3：自底向上动态规划

由递归解法分析可知，大问题可以划分为子问题+有限步骤解决，并且符合最优子结构、无后效性、重叠子问题。
这里的关键是梳理出子问题是经过怎样的步骤得到大问题，即可得到状态转移方程。

状态转移方程

设dp[i][j]为 s 的前i个字符是否能被 p 的前j个字符匹配。

s[i - 1] == p[j - 1]时，dp[i][j] = dp[i - 1][j - 1]
s[i - 1] != p[j - 1]时：
- p[j - 1] != '.' && p[j - 1] != '*'时，dp[i][j] = false。
- p[j - 1] == '.'时：
  .可以匹配任意字符，跟s[i - 1] == p[j - 1]的处理情况一样，即：dp[i][j] = dp[i - 1][j - 1]
- p[j - 1] == '*'时：
  *可以匹配前面字符的0个或多个；
  - 匹配0次：dp[i][j] = dp[i][j - 2]
  - 匹配1次：dp[i][j] = dp[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.')

初始边界

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val ls = s.length
        val lp = p.length
        // dp[i][j]表示s的前i个字符否能与p的前j个字符匹配，i和j分别从0开始取值
        val dp = Array(ls + 1) { BooleanArray(lp + 1) { false } }
		// 0个字符跟0个字符是匹配的
        dp[0][0] = true
		// p中有*是可以匹配0个字符的，所以做一下初始化
        for (j in 2 until dp[0].size) {
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'
        }
        for (i in 1 until dp.size) {
            for (j in 1 until dp[i].size) {
                val si = i - 1
                val pi = j - 1
                if (p[pi] == '*') {
                    // 匹配0次，字符可以不相等
                    // 匹配1次，字符要相同
                    dp[i][j] = dp[i][j - 2]
                            || dp[i - 1][j] && (s[si] == p[pi - 1] || p[pi - 1] == '.')
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (s[si] == p[pi] || p[pi] == '.')
                }
            }
        }
        return dp[ls][lp]
    }
}

时间复杂度 O(mn)：m、n分别为s、p长度，填充二维dp数组所需的时间。

空间复杂度 O(mn)：二维dp数组占用的空间。

题目

题解