97. 交错字符串

题号：97
来源：LeetCode
难度：中等
标签：dp 字符串
语言：TypeScript
解法：1 个
作者：lmliheng
最近更新：2026-09-27

TypeScript · O(n*m) 时间 · O(n*m) 空间 · 更新于 2026-09-27

dp 由上方或左侧转移，比较对应字符

typescript

/**
 * @difficulty medium
 * @tags dp,字符串
 * @time O(n*m)
 * @space O(n*m)
 * @note dp 由上方或左侧转移，比较对应字符
 * @97. 交错字符串
 */

let s1: string = "aabcc"
let s2: string = "dbbca"
let s3: string = "aadbbcbcac"

let m: number = s1.length
let n: number = s2.length
let k: number = s3.length
if (m + n !== k) {
    console.log('不能组成s3')
}
//s1有i个元素，s2有j个元素 组成s3
let dp: boolean[][] = new Array(m+1).fill(false).map(() => new Array(n+1).fill(false))
console.log(dp)
//初始化
dp[0][0] = true
for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1]
}
for (let i = 1; i <= n; i++) {
    dp[0][i] = dp[0][i - 1] && s2[i - 1] === s3[i - 1]
}
for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1])
    }
}

console.log(dp)

export {};

源码：ts/leetcode/97. 交错字符串.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm

97. 交错字符串 ​

97. 交错字符串