Is a string an interleaving of two others?
Given strings s1, s2 and s3, return true if s3 can be
formed by merging all of s1 and all of s2, taking characters from each in their original order.
Examples
| Input | Output | Why |
|---|---|---|
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" | true | aa + dbbc + bc + a + c. |
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" | false | No merge works. |
s1 = "", s2 = "", s3 = "" | true | Empty merge. |
Constraints
- 0 ≤ s1.length, s2.length ≤ 100
- 0 ≤ s3.length ≤ 200
Hints
Hint 1
If the lengths do not add up, the answer is false.
Hint 2
ok[i][j] = can s3[:i + j] be made from s1[:i] and s2[:j]?
Hint 3
ok[i][j] = (ok[i − 1][j] and s1[i − 1] = s3[i + j − 1]) or (ok[i][j − 1] and s2[j − 1] = s3[i + j − 1]).
Where people lose marks
- Skipping the length check.
- Merging greedily, which fails when s1 and s2 offer the same next character.
- Using three indices as the state: k = i + j is determined by the other two.
Dry run on "aab","axy","aaxaby"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4s1 uses 0T0T1F2F3
Row 0: which prefixes of s2 combine with 0 characters of s1 to give the start of s3.
-
Step 2 / 4s1 uses 0T0T1F2F3s1 uses 1T0T1T2F3
Row 1: which prefixes of s2 combine with 1 character of s1 to give the start of s3.
-
Step 3 / 4s1 uses 0T0T1F2F3s1 uses 1T0T1T2F3s1 uses 2T0F1T2F3
Row 2: which prefixes of s2 combine with 2 characters of s1 to give the start of s3.
-
Step 4 / 4s1 uses 0T0T1F2F3s1 uses 1T0T1T2F3s1 uses 2T0F1T2F3s1 uses 3F0F1T2T3
Row 3: which prefixes of s2 combine with 3 characters of s1 to give the start of s3. ok[3][3] = true.
How to think about it
Once i characters of s1 and j of s2 have been used, the merged prefix is s3[:i + j], so the pair (i, j) is
the whole state. ok[i][j] is true when the last character of that prefix can come from s1 (it equals
s1[i − 1] and ok[i − 1][j]) or from s2 (it equals s2[j − 1] and
ok[i][j − 1]). A greedy merge fails whenever both strings offer the same character; the table keeps both
possibilities alive.
Complexity. Time O(|s1| · |s2|) · Space O(|s2|)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_interleave(s1, s2, s3):
n, m = len(s1), len(s2)
if n + m != len(s3):
return False
ok = [False] * (m + 1) # ok[j] for the current number i of s1 characters used
for i in range(n + 1):
for j in range(m + 1):
if i == 0 and j == 0:
ok[j] = True
continue
from_s1 = i > 0 and ok[j] and s1[i - 1] == s3[i + j - 1] # ok[j] still holds row i - 1
from_s2 = j > 0 and ok[j - 1] and s2[j - 1] == s3[i + j - 1]
ok[j] = from_s1 or from_s2
return ok[m]#include <string>
#include <vector>
bool solve(std::string s1, std::string s2, std::string s3) {
const int n = s1.size(), m = s2.size();
if (n + m != (int)s3.size()) return false;
std::vector<bool> ok(m + 1, false);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
if (i == 0 && j == 0) { ok[0] = true; continue; }
bool fromS1 = i > 0 && ok[j] && s1[i - 1] == s3[i + j - 1];
bool fromS2 = j > 0 && ok[j - 1] && s2[j - 1] == s3[i + j - 1];
ok[j] = fromS1 || fromS2;
}
return ok[m];
}class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length();
if (n + m != s3.length()) return false;
boolean[] ok = new boolean[m + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) { ok[0] = true; continue; }
boolean fromS1 = i > 0 && ok[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
boolean fromS2 = j > 0 && ok[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
ok[j] = fromS1 || fromS2;
}
return ok[m];
}
}function isInterleave(s1, s2, s3) {
const n = s1.length, m = s2.length;
if (n + m !== s3.length) return false;
const ok = new Array(m + 1).fill(false);
for (let i = 0; i <= n; i++)
for (let j = 0; j <= m; j++) {
if (i === 0 && j === 0) { ok[0] = true; continue; }
const fromS1 = i > 0 && ok[j] && s1[i - 1] === s3[i + j - 1]; // ok[j]: row i - 1
const fromS2 = j > 0 && ok[j - 1] && s2[j - 1] === s3[i + j - 1];
ok[j] = fromS1 || fromS2;
}
return ok[m];
}fn solve(s1: &str, s2: &str, s3: &str) -> bool {
let (a, b, c): (Vec<u8>, Vec<u8>, Vec<u8>) = (s1.bytes().collect(), s2.bytes().collect(), s3.bytes().collect());
let (n, m) = (a.len(), b.len());
if n + m != c.len() {
return false;
}
let mut ok = vec![false; m + 1];
for i in 0..=n {
for j in 0..=m {
if i == 0 && j == 0 {
ok[0] = true;
continue;
}
let from_s1 = i > 0 && ok[j] && a[i - 1] == c[i + j - 1];
let from_s2 = j > 0 && ok[j - 1] && b[j - 1] == c[i + j - 1];
ok[j] = from_s1 || from_s2;
}
}
ok[m]
}import Data.Array
solve :: String -> String -> String -> Bool
solve s1 s2 s3
| n + m /= length s3 = False
| otherwise = ok ! (n, m)
where
(n, m) = (length s1, length s2)
a = listArray (1, n) s1
b = listArray (1, m) s2
c = listArray (1, n + m) s3
-- a lazy table over (characters of s1 used, characters of s2 used)
ok = array ((0, 0), (n, m)) [((i, j), cell i j) | i <- [0 .. n], j <- [0 .. m]] :: Array (Int, Int) Bool
cell 0 0 = True
cell i j = (i > 0 && ok ! (i - 1, j) && a ! i == c ! (i + j)) || (j > 0 && ok ! (i, j - 1) && b ! j == c ! (i + j))Variants to try
- Return one valid merge (record which string each step came from).
- Count the ways to interleave.
- Three strings into a fourth.
Next problems
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Hard30 minWildcard pattern matching
In the pattern, ? matches one character and * matches any run, including none. Does the pattern match the whole string?
Open the problem → Medium20 minThe shortest common supersequence
The shortest string that contains both strings as subsequences. Every shared character can be written once: n + m − LCS.
Open the problem →Write a solution and run it against the real test table.
Keep going
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Hard30 minWildcard pattern matching
In the pattern, ? matches one character and * matches any run, including none. Does the pattern match the whole string?
Open the problem → Medium20 minThe shortest common supersequence
The shortest string that contains both strings as subsequences. Every shared character can be written once: n + m − LCS.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.