10. Regular Expression Matching

Problem

Implement regular expression matching with support for . and *.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Related Topics:

Dynamic Programming Backtracking String

Analysis

影响匹配的主要因素是 *：

• 当遇到 * 时，判断 p 前一个字符与 s 当前字符：

  • 若相等，p 不变，接着判断 s 的下一个字符。

  • 若不等，s 不变，接着判断 p 的下一个字符。

• 没有遇到 * 时，判断 p 当前字符与s 当前字符：

  • 若相等，判断 p 下一个字符与s 下一个字符。

  • 若不等，返回 false。

因为遍历时， * 扩展的数量是不确定的，例如：aaas 和 a*as，通常不会一步到位，需要涉及到回溯。

方法一：递归。遇到 * 时，两种情况都有可能得出正确结果，用 || 关联。没有遇到 * 时，只需判断一种情况。

方法二：DP。建立二维数组，遍历的同时，记录之前所有的匹配情况，依据这些情报，来确定当前的状态。

Code

递归

class Solution {

    fun isMatch(s: String, p: String): Boolean {

        return isMatch(s, 0, p, 0)
    }

    private fun isMatch(s: String, si: Int, p: String, pi: Int): Boolean {

        return when {
            si >= s.length && pi >= p.length ->
                true
            pi + 1 < p.length && p[pi + 1] == '*' ->
                (si < s.length && (p[pi] == s[si] || p[pi] == '.') && isMatch(s, si + 1, p, pi)) || isMatch(s, si, p, pi + 2)
            else ->
                pi < p.length && si < s.length && (p[pi] == s[si] || p[pi] == '.') && isMatch(s, si + 1, p, pi + 1)
        }
    }
}

Dynamic Programming

class Solution {

    fun isMatch(s: String, p: String): Boolean {

        val ns = " " + s
        val np = " " + p

        val dp = Array(ns.length) { BooleanArray(np.length) }
        dp[0][0] = true

        for (i in 1 until ns.length) {
            dp[i][0] = false
        }

        for (i in 1 until np.length) {
            dp[0][i] = np[i] == '*' && i > 1 && dp[0][i - 2]
        }

        for (i in 1 until ns.length) {
            for (j in 1 until np.length) {
                dp[i][j] = when {
                    np[j] == '*' -> ((ns[i] == np[j - 1] || np[j - 1] == '.') && dp[i - 1][j]) || (j > 1 && dp[i][j - 2])
                    else -> (ns[i] == np[j] || np[j] == '.') && dp[i - 1][j - 1]
                }
            }
        }

        return dp[ns.lastIndex][np.lastIndex]
    }
}