Interleaving String
The briefingthe full drill, in my own words
The drill: Two source strings and a candidate merge — decide whether the candidate could have been built by interleaving the two sources while keeping each source's own character order intact.
Two source strings and a third candidate string arrive, and the task is to decide whether the candidate could have been built by interleaving the two sources together — weaving their characters into one sequence while keeping each source's own internal character order untouched.
Characters from the two sources can be interleaved in any pattern, switching back and forth as often as needed, but a source's own characters always have to appear in the same order they started in. Every character from both sources has to be used exactly once, with nothing left over.
The output is just yes or no — whether at least one valid interleaving produces the candidate string.
- the candidate's length must equal the combined length of both sources
- strings stay short enough for an O(m·n) table
- characters from each source keep their original relative order
- the answer is a single true/false
The hintstake only what you need
HINT 1 THE NUDGE
If the candidate isn't even the right length, it can't be an interleaving — check that first. Otherwise, having consumed i characters from one source and j from the other always points at one exact position in the candidate: i + j.
HINT 2 THE STRUCTURE
At every step, the next character of the candidate has to come from the next unused character of source one or the next unused character of source two — never from further ahead in either.
HINT 3 ONE STEP FROM THE ANSWER
DP: dp[i][j] = true when the first i+j characters of the candidate can be built from the first i of s1 and first j of s2. It's true if (dp[i-1][j] and s1[i-1] matches) or (dp[i][j-1] and s2[j-1] matches).
Coach's boardthe pattern, step by step
s1='ab', s2='cd', s3='acbd'. dp[i][j] asks: can the first i+j chars of acbd come from the first i of s1 and first j of s2? dp[0][0]=true trivially.
The splitstwo paces, two languages
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(n + 1):
if i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
dp[i][j] = True
if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
dp[i][j] = True
return dp[m][n]class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
def dfs(i, j):
k = i + j
if i == m and j == n:
return True
if i < m and s1[i] == s3[k] and dfs(i + 1, j):
return True
if j < n and s2[j] == s3[k] and dfs(i, j + 1):
return True
return False
return dfs(0, 0)class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) {
return false;
}
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
}
if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
}
}
}
return dp[m][n];
}
}class Solution {
private String s1, s2, s3;
private int m, n;
public boolean isInterleave(String s1, String s2, String s3) {
this.s1 = s1;
this.s2 = s2;
this.s3 = s3;
m = s1.length();
n = s2.length();
if (m + n != s3.length()) {
return false;
}
return dfs(0, 0);
}
private boolean dfs(int i, int j) {
int k = i + j;
if (i == m && j == n) {
return true;
}
if (i < m && s1.charAt(i) == s3.charAt(k) && dfs(i + 1, j)) {
return true;
}
if (j < n && s2.charAt(j) == s3.charAt(k) && dfs(i, j + 1)) {
return true;
}
return false;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED