Interleaving String Algorithm

The Interleaving String Algorithm is an advanced programming technique that deals with the problem of determining if a target string can be formed by interleaving two given strings. Interleaving refers to the process of combining two strings by merging them in such a way that their characters maintain their original order. For example, if we have two strings s1 = "abc" and s2 = "def", the target string "adbecf" can be formed by interleaving s1 and s2, while the target string "adcbef" cannot. This problem is commonly found in the realm of dynamic programming as well as in string manipulation tasks, having applications in natural language processing, pattern matching, and more. To solve this problem, the Interleaving String Algorithm employs a dynamic programming approach, utilizing a 2D boolean array to store the results of subproblems. The dimensions of the array correspond to the lengths of the two input strings, and each cell (i, j) in the array represents whether the target string can be formed by interleaving the first i characters of the first string and the first j characters of the second string. By filling the array iteratively, using the base cases and transition rules, the final cell of the array will provide the answer to the problem. To optimize space complexity, the algorithm can be further improved by using a 1D array, rolling over the results of previous iterations. This makes the Interleaving String Algorithm an efficient and elegant solution for the interleaving string problem.
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        
        int M = s1.size();
        int N = s2.size();
        
        if (M + N != s3.size()) return false;
        
        vector<vector<bool>> dp(2, vector<bool>(N + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= N; j++) {
            if (s2[j-1] == s3[j-1])
                dp[0][j] = true;
            else
                break;
        }
        int T1 = 1, T2 = 0;
        for (int i = 1; i <= M; i++) {
            T1 ^= 1, T2 ^= 1;
            dp[T2][0] = dp[T1][0] && s1[i-1] == s3[i-1];
            for (int j = 1; j <= N; j++) {
                if (s3[i+j-1] == s1[i-1] && s3[i+j-1] == s2[j-1])
                    dp[T2][j] = dp[T1][j] | dp[T2][j-1];
                else if (s3[i+j-1] == s1[i-1] && s3[i+j-1] != s2[j-1])
                    dp[T2][j] = dp[T1][j];
                else if (s3[i+j-1] != s1[i-1] && s3[i+j-1] == s2[j-1])
                    dp[T2][j] = dp[T2][j-1];
                else 
                    dp[T2][j] = false;
            }
        }
        return dp[T2][N];
    }
};

LANGUAGE:

DARK MODE: