Check whether a string is a valid shuffle of two strings
Problem
Given strings s1, s2 and result, return true if result interleaves s1 and s2: it uses all their characters, and the characters of each string keep their original order.
Example 1
Input: s1 = "XY", s2 = "12", result = "1XY2" Output: true
Example 2
Input: s1 = "XY", s2 = "12", result = "Y1X2" Output: false
Y comes before X, which breaks s1’s order.
Also asked as: Write a Program to check whether a string is a valid shuffle of two strings or not
Test cases
Case 1
Input: "XY", "12", "1XY2" Expected: true
Case 2
Input: "XY", "12", "Y1X2" Expected: false
Case 3
Input: "AB", "CD", "ACBD" Expected: true
Case 4
Input: "AB", "CD", "ABC" Expected: false
Case 5
Input: "", "XY", "XY" Expected: true
Case 6
Input: "AB", "AC", "ACAB" Expected: true
Case 7
Input: "AB", "AC", "AACB" Expected: true
Case 8
Input: "AB", "AC", "ABCA" Expected: false
View solutionHide solution1 approach
1. Interleaving DP
Time O(n · m)Space O(n · m)
dp[i][j] is true when the first i characters of a and the first j of b can form the first i + j of result. The last character of that prefix came from a (then dp[i−1][j] must hold) or from b (then dp[i][j−1] must hold).
function isValidShuffle(a, b, result) { const n = a.length, m = b.length; if (n + m !== result.length) return false; const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(false)); dp[0][0] = true; for (let i = 0; i <= n; i++) { for (let j = 0; j <= m; j++) { const c = result[i + j - 1]; if (i > 0 && dp[i - 1][j] && a[i - 1] === c) dp[i][j] = true; if (j > 0 && dp[i][j - 1] && b[j - 1] === c) dp[i][j] = true; } } return dp[n][m];}A greedy two-pointer walk (take the next character from whichever string matches) is not enough: when a and b share characters it can commit to the wrong string. For a = "AB", b = "AC", result = "ACAB" it takes the first A from a and then fails, although the answer is true.