97. 交错字符串 - Kotlin 二维DP

Problem: 97. 交错字符串

思路

设dp[s1len][s2len] = true为s1的前s1len个字符和s2的前s2len个字符一共可以匹配s3的前s1len+s2len个字符

• 当前s1能够匹配的最后一个字符的索引为s1len-1
• 当前s2能够匹配的最后一个字符的索引为s2len-1
• 当前s3能够匹配的最后一个字符的索引为s1len+s2len-1且该字符等于上面两个中的其中一个字符，设该字符为chr

一般地，该状态可以由两种情况派生：

• 当dp[s1len-1][s2len] = true时，若s1[s1len-1]==chr，则当前状态为true
• 当dp[s1len][s2len-1] = true时，若s2[s2len-1]==chr，则当前状态为true

考虑两种特殊情况：

• 当s1+s2或者s2+s1可以直接串联构成s3时，可以直接返回true
• 当s1.length+s2.length!=s3.length时，可以直接返回false

复杂度

• 时间复杂度:
• 空间复杂度:

Code

class Solution
fun Solution.isInterleave(s1: String, s2: String, s3: String): Boolean {
    if (s1 + s2 == s3 || s2 + s1 == s3) return true
    if (s1.length + s2.length != s3.length) return false
    val dp = Array(s1.length + 1) { s1ptr -> BooleanArray(s2.length + 1) { s2ptr -> s1ptr == 0 && s2ptr == 0 } }
    for ((index, chr) in s3.withIndex()) {
        val len = index + 1
        for (s1len in 0..Math.min(len, s1.length)) {
            val s2len = len - s1len
            if (s1len <= s1.length && s2len <= s2.length) {
                if ((s1len > 0 && dp[s1len - 1][s2len] && s1[s1len - 1] == chr)
                    ||
                    (s2len > 0 && dp[s1len][s2len - 1] && s2[s2len - 1] == chr)
                ) {
                    dp[s1len][s2len] = true
                    if (len == s3.length) return true
                }
            }
        }
    }
    return false
}