Interleaving String

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, and len3, representing the lengths of str1, str2, and str3 respectively. Check if the length of str3 is equal to the sum of the lengths of str1 and str2. If not, return false since str3 cannot possibly be an interleaving.
• Use a boolean vector interleaved to keep track of whether certain segments of str2 can form an interleaving up to each index when combined with segments of str1.
• In a nested loop, iterate over all possible splits between str1 and str2:
  • If both indices (i and j) representing positions in str1 and str2 are zero, initialize interleaved[j] as true.
  • If only i is zero, check if the segment of str2 up to index j alone can match with str3 up to index i + j, updating interleaved[j] accordingly.
  • If only j is zero, perform a similar check for str1 and update interleaved[j].
  • Otherwise, update interleaved[j] to reflect whether its previous value or the value of interleaved[j-1] (indicating different possible interleavings from str1 and str2) matches with str3.
• Finally, return the last value in the interleaved vector, which indicates whether the full strings can be interleaved to form str3.

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 of str1 and str2. If not, mergedStr cannot be an interleaved string, and the function returns false immediately.

• Utilize a boolean array flags with a size of str2.length() + 1 to keep track of whether a substring of mergedStr can be formed by interleaving substrings of str1 and str2 up to certain lengths.

• Iterate over every possible prefix length of str1 and str2. For each combination of substrings lengths from str1 and str2 (denoted as i and j), update the flags array based on the following conditions:

  • If either i or j is 0, initialize flags[j] based on whether the previous characters in flags and corresponding characters in str2, or str1 match the current character in mergedStr.
  • For other values of i and j, set flags[j] to true if:
    • The current character in mergedStr matches the last character of the current str1 prefix and the remainder formed by interleaving is valid.
    • The current character in mergedStr matches the last character of the current str2 prefix and the remainder formed by interleaving is valid.

• The value at flags[str2.length()] will ultimately indicate whether the entire mergedStr can be formed by interleaving str1 and str2.

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, and str3 using strlen.
• If the length of str3 is not equal to the sum of the lengths of str1 and str2, it directly returns false, indicating that str3 cannot be an interleaving of str1 and str2.
• An array interleave of type bool with a size of length2 + 1 is initialized to store intermediate validation results.
• The memset function initializes all elements in the interleave array to false.

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 and idx2 are zero, then the starting point is set to true as there is no character to check yet.
• For the edge cases where idx1 is zero or idx2 is zero, the function verifies if continuing from previous characters will still satisfy interleaving up to the current index by comparing parts from str2 or str1 with str3 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.

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 of str1 and str2. If not, it immediately returns false.
• Initialize a boolean array check with a length of str2.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 through str1 and y through str2. The function updates the check array based on conditions:
  • When both x and y are zero, set check[y] to true.
  • If only x is zero, set check[y] based on the comparison between the last character of the section of str2 considered so far and the corresponding character in combined.
  • If only y is zero, adjust check[y] based on the comparison between the last character of the section of str1 considered so far and the corresponding character in combined.
  • For other values of x and y, set check[y] to true if either of the following conditions are met:
    • check[y] is true, and the character from str1 matches the corresponding character in combined.
    • The previous value check[y-1] is true, and the character from str2 matches the corresponding character in combined.
• Finally, return the value of check[str2.length] to determine if combined can indeed be formed by interleaving str1 and str2.

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 and str2 matches the length of str3. If not, it returns False immediately.
• A one-dimensional list dp_table is utilized to keep track of the interleaving status. This list is initialized with False 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 or str2, the interleaving condition is naturally True (dp_table[0] is True).
• For characters from str2, it updates the state based on previous values in the dp_table.
• For characters from str1, it uses either the current or previous values from the dp_table to update the interleaving state.
• Each state dp_table[idx2] is updated based on whether str1[idx1-1] or str2[idx2-1] matches with str3[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.