Interleaving Two Strings

The problem is to determine whether a given string s3 can be formed by interleaving two other strings s1 and s2. The interleaving of the two strings must preserve the order of characters in both strings.

Recursive Approach
The first method used is the recursive approach. This approach tries to match each character of s3 with either s1 or s2. If a match is found, the function recursively checks the remaining characters.

bool solveUsingRecursion(string &s1, string &s2, string &s3, int i, int j, int k) {
  if (i >= s1.length() && j >= s2.length() && k >= s3.length()) {
    return true;
  }

  bool flag = false;

  // Check if the current character of s1 matches s3
  if (i < s1.length() && s1[i] == s3[k]) {
    flag = flag || solveUsingRecursion(s1, s2, s3, i + 1, j, k + 1);
  }

  // Check if the current character of s2 matches s3
  if (j < s2.length() && s2[j] == s3[k]) {
    flag = flag || solveUsingRecursion(s1, s2, s3, i, j + 1, k + 1);
  }

  return flag;
}

In this code:
The base case checks if all characters have been matched. If so, it returns true.
The function tries to match s3[k] with s1[i] or s2[j]. If a match is found, the function recursively checks the rest.
Time Complexity: The time complexity of this approach is exponential,
(O(2^{n+m})), due to the branching factor of checking two possibilities at each step.

Memoization Approach
To optimize the recursive approach, we can use memoization to store the results of subproblems and avoid redundant calculations.

bool solveUsingMemoization(string &s1, string &s2, string &s3, int i, int j, int k, vector<vector<vector<int>>> &dp) {
  if (i >= s1.length() && j >= s2.length() && k >= s3.length()) {
    return true;
  }

  if (dp[i][j][k] != -1) {
    return dp[i][j][k];
  }

  bool flag = false;

  if (i < s1.length() && s1[i] == s3[k]) {
    flag = flag || solveUsingMemoization(s1, s2, s3, i + 1, j, k + 1, dp);
  }

  if (j < s2.length() && s2[j] == s3[k]) {
    flag = flag || solveUsingMemoization(s1, s2, s3, i, j + 1, k + 1, dp);
  }

  return dp[i][j][k] = flag;
}

Here, a 3D dp table stores the results of subproblems, reducing the overall time complexity to O(n×m×p), where n, m, and p are the lengths of s1, s2, and s3, respectively.

Tabulation Approach
The next optimization is using tabulation, where we build the solution iteratively rather than recursively.

bool solveUsingTabulation(string &s1, string &s2, string &s3) {
  int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
  vector<vector<vector<int>>> dp(len1 + 1, vector<vector<int>>(len2 + 1, vector<int>(len3 + 1, 0)));

  dp[len1][len2][len3] = true;

  for (int i = len1; i >= 0; i--) {
    for (int j = len2; j >= 0; j--) {
      for (int k = len3; k >= 0; k--) {
        if (i >= len1 && j >= len2 && k >= len3) {
          continue;
        }

        bool flag = false;

        if (i < len1 && s1[i] == s3[k]) {
          flag = flag || dp[i + 1][j][k + 1];
        }

        if (j < len2 && s2[j] == s3[k]) {
          flag = flag || dp[i][j + 1][k + 1];
        }

        dp[i][j][k] = flag;
      }
    }
  }

  return dp[0][0][0];
}

This method iteratively fills up a DP table. The time complexity remains the same as memoization, but it is easier to understand and debug.

Space-Optimized Solution
Finally, to reduce space complexity, we use a 1D DP array.

bool isInterleaveOptimized(string a, string b, string c) {
  if (a.length() < b.length()) {
    swap(a, b);
  }

  int n1 = a.length(), n2 = b.length(), n3 = c.length();
  vector<bool> dp(n2 + 1, false);

  if (n1 + n2 != n3) {
    return false;
  }

  for (int i = 0; i <= n1; i++) {
    for (int j = 0; j <= n2; j++) {
      if (i == 0 && j == 0) {
        dp[j] = true;
      } else if (i == 0) {
        dp[j] = dp[j - 1] && (b[j - 1] == c[j - 1]);
      } else if (j == 0) {
        dp[j] = dp[j] && (a[i - 1] == c[i - 1]);
      } else {
        dp[j] = (dp[j] && a[i - 1] == c[i + j - 1]) || (dp[j - 1] && b[j - 1] == c[i + j - 1]);
      }
    }
  }

  return dp[n2];
}

By reducing the problem to a single 1D DP array, we save space while still achieving the desired result.
The space complexity is reduced to O(min(n,m))

Conclusion
This problem can be solved using various methods, each with its trade-offs between time and space complexity. Starting with a recursive approach helps build an understanding, which can be optimized step-by-step to improve efficiency. The final solution is a space-optimized dynamic programming approach, which efficiently checks if s3 is an interleaving of s1 and s2.