Loading problem…
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that the substrings are concatenated in an alternating fashion to form the interleaving. The two strings s and t are said to be interleaving if the resulting string preserves the relative order of the characters within each of the strings.
Example 1
Input: s1 = aabcc, s2 = dbbca, s3 = aadbbcbcac
Output: true
Explanation: Split s1 into "aa" + "bc" + "c" and s2 into "dbbc" + "a". Alternating them gives "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac", and each string keeps its own order.
Example 2
Input: s1 = aabcc, s2 = dbbca, s3 = aadbbbaccc
Output: false
Explanation: No way of alternating pieces of s1 and s2 produces "aadbbbaccc". For example, it has three b's in a row, but the only b's are one in s1 and two in s2, and those can't all come before the 'a' that follows them while keeping each string's order.
Example 3
Input: s1 = a, s2 = b, s3 = ab
Output: true
Explanation: Taking "a" from s1 and then "b" from s2 gives "ab".
Let dp[i][j] mean the first i characters of s1 and the first j characters of s2 can interleave to form the first i+j characters of s3. A cell is reachable if the matching character of s3 came from s1 (extending dp[i-1][j]) or from s2 (extending dp[i][j-1]).
Run checks all cases above. Submit evaluates all test cases.