题解|#10. 正则表达式匹配#

https://leetcode-cn.com/problems/regular-expression-matching/

使用动态规划。dp[i][j]表示s的前i个字符能否被p的前j个字符匹配到
无特殊情况下。当s[i-1]==p[j-1]时，dp[i][j]=dp[i-1][j-1]。即当第i个字符(i-1位)同第j个字符(j-1位)匹配时，当前dp能否满足取决于分别将s和p去掉一个字符
.：匹配任意字符。所以在判断相等时(isCharMatch)进行处理。
*：匹配零至多个。分两种情况
- 匹配零次：dp[i][j]=dp[i][j-2]。此时*及前一个字符不生效
- 匹配至少一次：则必须满足s[i-1]==p[j-2](p[j-1]==*)。则dp[i][j]=dp[i-1][j]
- 代码中的替换写法dp[sLeft][pLeft] = dp[sLeft][pLeft - 2] || if (isCharMatch(s, p, sLeft, pLeft - 1)) dp[sLeft - 1][pLeft] else false
注意循环时，i从0开始，j从1开始

import org.junit.Test

//给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//
// 
// '.' 匹配任意单个字符 
// '*' 匹配零个或多个前面的那一个元素 
// 
//
// 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 
// 
//
// 示例 1： 
//
// 
//输入：s = "aa" p = "a"
//输出：false
//解释："a" 无法匹配 "aa" 整个字符串。
// 
//
// 示例 2: 
//
// 
//输入：s = "aa" p = "a*"
//输出：true
//解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
// 
//
// 示例 3： 
//
// 
//输入：s = "ab" p = ".*"
//输出：true
//解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
// 
//
// 示例 4： 
//
// 
//输入：s = "aab" p = "c*a*b"
//输出：true
//解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
// 
//
// 示例 5： 
//
// 
//输入：s = "mississippi" p = "mis*is*p*."
//输出：false 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 20 
// 0 <= p.length <= 30 
// s 可能为空，且只包含从 a-z 的小写字母。 
// p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 
// 保证每次出现字符 * 时，前面都匹配到有效的字符 
// 
// Related Topics 递归 字符串 动态规划 
// 👍 2219 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionIsMatch {
    @Test
    fun main() {
        println(isMatch("aab", "c*a*b"))
    }

    /***
     * dp[i][j] 表示 s 的前 i 个字符能否被 p 的前 j 个字符匹配
     * 访问的时候，需要使用 -1
     */
    fun isMatch(s: String, p: String): Boolean {
        var dp = Array(s.length + 1) { BooleanArray(p.length + 1) }
        dp[0][0] = true;
        for (sLeft in 0 until s.length + 1) {
            for (pLeft in 1 until p.length + 1) {
                if ('*' == p[pLeft - 1]) {
                    // * 要么s没有匹配的，要么s去了一个后还是匹配
                    // * 匹配至少一次， 则p当前位同*前一位匹配
                    if (isCharMatch(s, p, sLeft, pLeft - 1)) {
                        // 可以匹配0或多次
                        // 计算了匹配0次 ||
                        // 匹配多次， 则代表s前一位也匹配
                        dp[sLeft][pLeft] = dp[sLeft][pLeft - 2] || dp[sLeft - 1][pLeft]
                    } else {
                        // * 只能 匹配零次  则去了*及前一位，判断是否匹配
                        dp[sLeft][pLeft] = dp[sLeft][pLeft - 2]
                    }
                } else {
                    if (isCharMatch(s, p, sLeft, pLeft)) {
                        dp[sLeft][pLeft] = dp[sLeft - 1][pLeft - 1]
                    }
                }
            }
        }
        // for (i in s.indices) {
        //     for (j in p.indices) {
        //         print(dp[i + 1][j + 1])
        //         print("\t")
        //     }
        //     println()
        // }
        // var result = false
        return dp[s.length][p.length]
    }

    /***
     * 检查两个的第 sLength-1 同 pLength-1 是否相等
     *
     * @param s 待匹配字符
     * @param p 正则表达式
     * @param sLength 检查s的第 sLength-1 个元素
     * @param pLength 检查p的第 sLength-1 个元素
     */
    private fun isCharMatch(s: String, p: String, sLength: Int, pLength: Int): Boolean {
        // p 从 1 开始 ，不可能为0
        if (sLength == 0 || pLength == 0) {
            return false
        }
        if ('.' == p[pLength - 1]) {
            return true
        }
        return s[sLength - 1] == p[pLength - 1]
        // TODO("Not yet implemented")
    }
}
//leetcode submit region end(Prohibit modification and deletion)