Check whether a string is a valid shuffle of two strings

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.