Interleaving String

The key idea

Build the answer character by character. To form the first i + j characters of s3 from the first i of s1 and the first j of s2, the very last character must come from either s1 or s2. So dp[i][j] is true when its left neighbor is true and s2[j-1] matches, OR its up neighbor is true and s1[i-1] matches. This 2-D table removes the exponential branching of trying every split.

Problem

You are given three strings s1, s2, and s3. Return true if s3 is formed by an interleaving of s1 and s2, and false otherwise.

An interleaving of two strings s and t is a way of splitting each of them into pieces and joining all the pieces in an order that keeps the original left-to-right order within each string. Formally, s can be split as s = a1 + a2 + ... + an and t as t = b1 + b2 + ... + bm, and the interleaving is a1 + b1 + a2 + b2 + ... (the pieces alternate but the relative order inside s and inside t is preserved). A necessary condition is that the total length matches: s1.length + s2.length must equal s3.length.

Constraints

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.

Examples

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

Input: s1 = "", s2 = "", s3 = "" Output: true

Complexity

Time: O(m * n) Space: O(m * n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →