Math Dynamic Programming
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) = aabcc
second (string) = dbbca
target (string) = aadbbcbcac
Return:
(boolean) true
Example 2
Input:
first (string) = aabcc
second (string) = dbbca
target (string) = aadbbbaccc
Return:
(boolean) false
Example 3
Input:
first (string) = abc
second (string) = def
target (string) = adbcef
Return:
(boolean) true

Use 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)]
Run your code to see the result.