Proficient Level
Implement the interleavingStringCheck method that checks whether one string is formed by interleaving two other strings.
You are given three strings: first, second, and target. Return true if target can be formed by interleaving characters from the first two strings.
The relative order of characters from each original string must be preserved. Characters may be taken alternately or in longer groups.
Example 1
Input
first (string) =
aabccsecond (string) =
dbbcatarget (string) =
aadbbcbcacReturns (boolean)
trueExample 2
Input
first (string) =
aabccsecond (string) =
dbbcatarget (string) =
aadbbbacccReturns (boolean)
falseExample 3
Input
first (string) =
abcsecond (string) =
deftarget (string) =
adbcefReturns (boolean)
trueUse dynamic programming over indexes of the first two strings.
Let dp[i][j] mean that the first i characters of first and the first j characters of second can form the first i + j characters of target. Each state can come from taking the next character from either string if it matches the target position.
If the total lengths do not match, return false immediately.
Pseudocode:
function interleavingStringCheck(first, second, target):
if length(first) + length(second) != length(target):
return false
create dp table filled with false
dp[0][0] = true
for i from 0 to length(first):
for j from 0 to length(second):
position = i + j - 1
if i > 0 and dp[i - 1][j] and first[i - 1] == target[position]:
dp[i][j] = true
if j > 0 and dp[i][j - 1] and second[j - 1] == target[position]:
dp[i][j] = true
return dp[length(first)][length(second)]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run