
Problem Statement
The task is to determine whether a string s3
can be formed by interleaving two other strings s1
and s2
. The concept of interleaving here involves splitting s1
and s2
into several substrings and reassembling these pieces intercalatedly to produce s3
. Specifically, s1
and s2
are divided into substrings such that their concatenation in an alternate fashion results in s3
. The interleaving pattern should either start with a substring from s1
followed by one from s2
or vice versa, continuing this pattern throughout. It's also required that the absolute difference in the number of pieces into which s1
and s2
are divided does not exceed one.
Examples
Example 1
Input:
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output:
true
Explanation:
One way to obtain s3 is: Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a". Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac". Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2
Input:
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output:
false
Explanation:
Notice how it is impossible to interleave s2 with any other string to obtain s3.
Example 3
Input:
s1 = "", s2 = "", s3 = ""
Output:
true
Constraints
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1
,s2
, ands3
consist of lowercase English letters.
Approach and Intuition
The key to solving the problem of checking if s3
is an interleaving of s1
and s2
lies in exploring all possible interleaved combinations that s1
and s2
can produce and seeing if any of these match s3
. Below follows a logical breakdown based on insights from the examples provided:
Dynamic Programming Table Initialization:
- Consider a 2D array
dp
wheredp[i][j]
indicates whether the firsti
characters ofs1
and the firstj
characters ofs2
can interleave to form the firsti+j
characters ofs3
. - Initialize
dp[0][0] = true
(empty strings interleaving to form an empty string).
- Consider a 2D array
Fill the DP Table:
- For each character position in
s1
ands2
, determine if that character can extend an existing interleaving froms3
. - Specifically, check if
dp[i][j] = true
under two conditions:- If the last character added from
s1
matches the current character ins3
anddp[i-1][j]
was true. - If the last character added from
s2
matches the current character ins3
anddp[i][j-1]
was true.
- If the last character added from
- For each character position in
Edge Cases:
- When one of
s1
ors2
is empty,s3
should be entirely made of the other non-empty string. - If the combined length of
s1
ands2
does not match the length ofs3
, it’s impossible fors3
to be an interleaving ofs1
ands2
.
- When one of
Examples from user input demonstrate this logic:
Example 1:
s1 = "aabcc"
,s2 = "dbbca"
,s3 = "aadbbcbcac"
- Through careful selection and interleaving of substrings from
s1
ands2
,s3
is achievable.
Example 2:
- A mismatch in desired subsequence characters points to
s3
not being a possible interleaving.
- A mismatch in desired subsequence characters points to
Example 3:
- All strings are empty. Trivially, an empty string is an interleaving of two empty strings.
Through this approach, one can systematically determine whether s3
is a result of interleaving s1
and s2
by filling up a dynamic programming table and consulting its last cell to check for feasibility. This method ensures that all potential segmentations and interleavings are considered.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
bool checkInterleavings(string str1, string str2, string str3) {
int len1 = str1.length(), len2 = str2.length(), len3 = str3.length();
if (len3 != len1 + len2) {
return false;
}
vector<bool> interleaved(len2 + 1, false);
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 && j == 0) {
interleaved[j] = true;
} else if (i == 0) {
interleaved[j] = interleaved[j - 1] && str2[j - 1] == str3[i + j - 1];
} else if (j == 0) {
interleaved[j] = interleaved[j] && str1[i - 1] == str3[i + j - 1];
} else {
interleaved[j] = (interleaved[j] && str1[i - 1] == str3[i + j - 1]) ||
(interleaved[j - 1] && str2[j - 1] == str3[i + j - 1]);
}
}
}
return interleaved[len2];
}
};
The provided C++ solution addresses the problem of determining if a string str3
is an interleaving of two other strings str1
and str2
. The code relies on dynamic programming to efficiently solve the problem, represented by the function checkInterleavings
.
- Start by declaring and initializing three integer variables,
len1
,len2
, andlen3
, representing the lengths ofstr1
,str2
, andstr3
respectively. Check if the length ofstr3
is equal to the sum of the lengths ofstr1
andstr2
. If not, return false sincestr3
cannot possibly be an interleaving. - Use a boolean vector
interleaved
to keep track of whether certain segments ofstr2
can form an interleaving up to each index when combined with segments ofstr1
. - In a nested loop, iterate over all possible splits between
str1
andstr2
:- If both indices (i and j) representing positions in
str1
andstr2
are zero, initializeinterleaved[j]
as true. - If only
i
is zero, check if the segment ofstr2
up to indexj
alone can match withstr3
up to indexi + j
, updatinginterleaved[j]
accordingly. - If only
j
is zero, perform a similar check forstr1
and updateinterleaved[j]
. - Otherwise, update
interleaved[j]
to reflect whether its previous value or the value ofinterleaved[j-1]
(indicating different possible interleavings fromstr1
andstr2
) matches withstr3
.
- If both indices (i and j) representing positions in
- Finally, return the last value in the
interleaved
vector, which indicates whether the full strings can be interleaved to formstr3
.
This method provides an efficient solution to the problem by using a single-dimensional DP table instead of a two-dimensional one, optimizing the space complexity. The overall approach ensures checks at each position if the characters of str1
and str2
can compose str3
in a recursive manner while storing the states to avoid redundant calculations.
public class Solution {
public boolean checkInterleaved(String str1, String str2, String mergedStr) {
if (mergedStr.length() != str1.length() + str2.length()) {
return false;
}
boolean[] flags = new boolean[str2.length() + 1];
for (int i = 0; i <= str1.length(); i++) {
for (int j = 0; j <= str2.length(); j++) {
if (i == 0 && j == 0) {
flags[j] = true;
} else if (i == 0) {
flags[j] = flags[j - 1] &&
str2.charAt(j - 1) == mergedStr.charAt(i + j - 1);
} else if (j == 0) {
flags[j] = flags[j] && str1.charAt(i - 1) == mergedStr.charAt(i + j - 1);
} else {
flags[j] = (flags[j] &&
str1.charAt(i - 1) == mergedStr.charAt(i + j - 1)) ||
(flags[j - 1] && str2.charAt(j - 1) == mergedStr.charAt(i + j - 1));
}
}
}
return flags[str2.length()];
}
}
The provided Java solution tackles the problem of determining whether a string mergedStr
can be formed by interleaving two other strings str1
and str2
. Here’s how the solution efficiently approaches the problem:
First, ensure that the length of
mergedStr
is exactly equal to the sum of the lengths ofstr1
andstr2
. If not,mergedStr
cannot be an interleaved string, and the function returns false immediately.Utilize a boolean array
flags
with a size ofstr2.length() + 1
to keep track of whether a substring ofmergedStr
can be formed by interleaving substrings ofstr1
andstr2
up to certain lengths.Iterate over every possible prefix length of
str1
andstr2
. For each combination of substrings lengths fromstr1
andstr2
(denoted asi
andj
), update theflags
array based on the following conditions:- If either
i
orj
is 0, initializeflags[j]
based on whether the previous characters inflags
and corresponding characters instr2
, orstr1
match the current character inmergedStr
. - For other values of
i
andj
, setflags[j]
to true if:- The current character in
mergedStr
matches the last character of the currentstr1
prefix and the remainder formed by interleaving is valid. - The current character in
mergedStr
matches the last character of the currentstr2
prefix and the remainder formed by interleaving is valid.
- The current character in
- If either
The value at
flags[str2.length()]
will ultimately indicate whether the entiremergedStr
can be formed by interleavingstr1
andstr2
.
The core idea is to dynamically build up the solution using previously computed results, greatly reducing the complexity and improving efficiency compared to a naive approach. This smart design ensures the solution is both optimal and clean, focusing solely on whether interleaving is possible without constructing the actual interleaved string.
bool checkInterleave(char* str1, char* str2, char* str3) {
int length1 = strlen(str1), length2 = strlen(str2), length3 = strlen(str3);
if (length3 != length1 + length2) {
return false;
}
bool interleave[length2 + 1];
memset(interleave, false, sizeof(interleave));
for (int idx1 = 0; idx1 <= length1; idx1++) {
for (int idx2 = 0; idx2 <= length2; idx2++) {
if (idx1 == 0 && idx2 == 0) {
interleave[idx2] = true;
} else if (idx1 == 0) {
interleave[idx2] = interleave[idx2 - 1] && str2[idx2 - 1] == str3[idx1 + idx2 - 1];
} else if (idx2 == 0) {
interleave[idx2] = interleave[idx2] && str1[idx1 - 1] == str3[idx1 + idx2 - 1];
} else {
interleave[idx2] = (interleave[idx2] && str1[idx1 - 1] == str3[idx1 + idx2 - 1]) ||
(interleave[idx2 - 1] && str2[idx2 - 1] == str3[idx1 + idx2 - 1]);
}
}
}
return interleave[length2];
}
The C function checkInterleave
checks whether a string str3
is an interleaving of two other strings, str1
and str2
. An interleaving string contains all characters from both strings and maintains the relative order of characters from each string.
- The function begins by calculating the lengths of
str1
,str2
, andstr3
usingstrlen
. - If the length of
str3
is not equal to the sum of the lengths ofstr1
andstr2
, it directly returnsfalse
, indicating thatstr3
cannot be an interleaving ofstr1
andstr2
. - An array
interleave
of typebool
with a size oflength2 + 1
is initialized to store intermediate validation results. - The
memset
function initializes all elements in theinterleave
array tofalse
.
The core part of the function is a nested loop iterating over each character of str1
and str2
. The loops perform the following checks:
- If both indexes
idx1
andidx2
are zero, then the starting point is set totrue
as there is no character to check yet. - For the edge cases where
idx1
is zero oridx2
is zero, the function verifies if continuing from previous characters will still satisfy interleaving up to the current index by comparing parts fromstr2
orstr1
withstr3
respectively. - For general cases, the function checks two conditions:
- If continuing from the last character of
str1
is possible. - Or, if continuing from the last character of
str2
is possible.
- If continuing from the last character of
The function ultimately returns the value of interleave[length2]
, which represents whether str3
can be constructed by interleaving str1
and str2
entirely by index length2
of str2
.
var interleavedStrings = function (str1, str2, combined) {
if (combined.length !== str1.length + str2.length) {
return false;
}
let check = new Array(str2.length + 1).fill(false);
for (let x = 0; x <= str1.length; x++) {
for (let y = 0; y <= str2.length; y++) {
if (x === 0 && y === 0) {
check[y] = true;
} else if (x === 0) {
check[y] = check[y - 1] && str2[y - 1] === combined[x + y - 1];
} else if (y === 0) {
check[y] = check[y] && str1[x - 1] === combined[x + y - 1];
} else {
check[y] =
(check[y] && str1[x - 1] === combined[x + y - 1]) ||
(check[y - 1] && str2[y - 1] === combined[x + y - 1]);
}
}
}
return check[str2.length];
};
The provided JavaScript function interleavedStrings
determines if the string combined
can be formed by interleaving the characters of two other strings str1
and str2
. This function uses dynamic programming as its underlying solution approach.
- The function starts by checking if the
combined
string's length is equal to the sum of the lengths ofstr1
andstr2
. If not, it immediately returns false. - Initialize a boolean array
check
with a length ofstr2.length + 1
and set all values to false. This array helps keep track of previously computed results to avoid redundant calculations. - Utilize nested loops where
x
iterates throughstr1
andy
throughstr2
. The function updates thecheck
array based on conditions:- When both
x
andy
are zero, setcheck[y]
to true. - If only
x
is zero, setcheck[y]
based on the comparison between the last character of the section ofstr2
considered so far and the corresponding character incombined
. - If only
y
is zero, adjustcheck[y]
based on the comparison between the last character of the section ofstr1
considered so far and the corresponding character incombined
. - For other values of
x
andy
, setcheck[y]
to true if either of the following conditions are met:check[y]
is true, and the character fromstr1
matches the corresponding character incombined
.- The previous value
check[y-1]
is true, and the character fromstr2
matches the corresponding character incombined
.
- When both
- Finally, return the value of
check[str2.length]
to determine ifcombined
can indeed be formed by interleavingstr1
andstr2
.
The dynamic programming approach helps optimize the interleaving check by breaking it down into smaller subproblems, each defining a possible interleaving at different stages with entries x
and y
. This leads to a more efficient solution compared to naive recursive methods.
class Solution:
def checkInterleaved(self, str1: str, str2: str, str3: str) -> bool:
if len(str3) != len(str1) + len(str2):
return False
dp_table = [False] * (len(str2) + 1)
for idx1 in range(len(str1) + 1):
for idx2 in range(len(str2) + 1):
if idx1 == 0 and idx2 == 0:
dp_table[idx2] = True
elif idx1 == 0:
dp_table[idx2] = dp_table[idx2 - 1] and str2[idx2 - 1] == str3[idx1 + idx2 - 1]
elif idx2 == 0:
dp_table[idx2] = dp_table[idx2] and str1[idx1 - 1] == str3[idx1 + idx2 - 1]
else:
dp_table[idx2] = (dp_table[idx2] and str1[idx1 - 1] == str3[idx1 + idx2 - 1]) or (
dp_table[idx2 - 1] and str2[idx2 - 1] == str3[idx1 + idx2 - 1]
)
return dp_table[len(str2)]
This Python solution involves a function checkInterleaved
that determines if a string str3
is an interleaving of two other strings, str1
and str2
. The function uses dynamic programming to solve the problem efficiently:
- Initially, it checks if the combined length of
str1
andstr2
matches the length ofstr3
. If not, it returnsFalse
immediately. - A one-dimensional list
dp_table
is utilized to keep track of the interleaving status. This list is initialized withFalse
values, representing that no interleaving has been determined yet. - The list size corresponds to the length of
str2
plus one (for base cases).
The solution iteratively fills the dp_table
using conditions based on character matches between str3
and the respective characters of str1
and str2
:
- It sets the initial condition where if no characters are taken from either
str1
orstr2
, the interleaving condition is naturallyTrue
(dp_table[0]
isTrue
). - For characters from
str2
, it updates the state based on previous values in thedp_table
. - For characters from
str1
, it uses either the current or previous values from thedp_table
to update the interleaving state. - Each state
dp_table[idx2]
is updated based on whetherstr1[idx1-1]
orstr2[idx2-1]
matches withstr3[idx1+idx2-1]
, indicating if a valid interleaving can include the current character.
Finally, the function returns the value at dp_table[len(str2)]
, which indicates if the entire str3
can be formed by interleaving all characters of str1
and str2
. This approach provides a clear and efficient solution to the interleaving string problem using dynamic programming principles.
No comments yet.