Return whether s3 can be formed by interleaving s1 and s2: splitting both into pieces and merging the pieces while keeping each string's characters in order.
dp[i][j] = can the first i chars of s1 and the first j of s2 form the first i+j of s3? Come from above if s1[i−1] matches, or from the left if s2[j−1] matches.
1function isInterleave(s1: string, s2: string, s3: string): boolean {2const m = s1.length, n = s2.length;3if (m + n !== s3.length) return false;4const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));5dp[0][0] = true;6for (let i = 0; i <= m; i++)7for (let j = 0; j <= n; j++) {8if (i && s1[i - 1] === s3[i + j - 1] && dp[i - 1][j]) dp[i][j] = true;9if (j && s2[j - 1] === s3[i + j - 1] && dp[i][j - 1]) dp[i][j] = true;10}11return dp[m][n];12}
| ∅ | a | x | y | |
|---|---|---|---|---|
| ∅ | T | |||
| a | ||||
| a | ||||
| b |
Two empty prefixes make an empty prefix.
Space: play/pause · ←/→: step