题解|#44. 通配符匹配#

还是使用动态规划， 基本思路同10. 正则表达式匹配

当为*时使用了for循环。是因为此时的*能匹配任意字符。所以只要s中能匹配p去了*的部分，dp[i][j]就成立

for (k in 0..s.length) {
  dp[i][j] = dp[k][j - 1] || dp[i][j]
  if (dp[i][j]) {
    break
  }
}

import org.junit.Test

//给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
//
// '?' 可以匹配任何单个字符。
//'*' 可以匹配任意字符串（包括空字符串）。
// 
//
// 两个字符串完全匹配才算匹配成功。 
//
// 说明: 
//
// 
// s 可能为空，且只包含从 a-z 的小写字母。 
// p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。 
// 
//
// 示例 1: 
//
// 输入:
//s = "aa"
//p = "a"
//输出: false
//解释: "a" 无法匹配 "aa" 整个字符串。 
//
// 示例 2: 
//
// 输入:
//s = "aa"
//p = "*"
//输出: true
//解释: '*' 可以匹配任意字符串。
// 
//
// 示例 3: 
//
// 输入:
//s = "cb"
//p = "?a"
//输出: false
//解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
// 
//
// 示例 4: 
//
// 输入:
//s = "adceb"
//p = "*a*b"
//输出: true
//解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
// 
//
// 示例 5: 
//
// 输入:
//s = "acdcb"
//p = "a*c?b"
//输出: false 
// Related Topics 贪心 递归 字符串 动态规划 
// 👍 714 👎 0

@Test
fun main() {
    // println(isMatch("acdcb", "a*c?b"))
    // assertEquals(false, isMatch("acdcb", "a*c?b"), "false")
    // println(isMatch("aa", "a"))
    // assertEquals(false, isMatch("aa", "a"), "false")
    // println(isMatch("aa", "*"))
    // assertEquals(true, isMatch("aa", "*"), "false")
    // println(isMatch("cb", "?a"))
    // assertEquals(false, isMatch("cb", "?a"), "false")
    // println(isMatch("adceb", "*a*b"))
    // assertEquals(true, isMatch("adceb", "*a*b"), "false")
    // println(isMatch("aab", "c*a*b"))
}


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionIsMatch1 {
    fun isMatch(s: String, p: String): Boolean {
        // s的前i个是否匹配p的前i个。
        val dp = Array(s.length + 1) { BooleanArray(p.length + 1) }
        dp[0][0] = true
        for (i in 0..s.length) {
            for (j in 1..p.length) {
                if (i == 0) {
                    if ('*' == p[j - 1]) {
                        dp[i][j] = dp[i][j - 1]
                    } else {
                        dp[i][j] = false
                    }
                } else {
                    // 可匹配0或多个字符
                    if ('*' == p[j - 1]) {
                        // 因为*是贪婪匹配，所以需要遍历所有的 dp[?][j - 1]
                        for (k in 0..s.length) {
                            dp[i][j] = dp[k][j - 1] || dp[i][j]
                            if (dp[i][j]) {
                                break
                            }
                        }
                        continue
                    }
                    if (s[i - 1] == p[j - 1] || '?' == p[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1]
                    }
                }
                // if (!dp[i][j]) {
                //     break
                // }
            }
        }
        return dp[s.length][p.length]
        TODO()
    }
}
//leetcode submit region end(Prohibit modification and deletion)