Fix for interleaving-string

[raymowu]

Bug Report for https://neetcode.io/problems/interleaving-string

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

using solution 5, dynamic programming optimal, all test cases pass however there is a missing test case: s1 = "aaa", s2 = "bbb", s3 = "bbbbbb" that does not pass.
Current code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        if (n < m) {
            swap(s1, s2);
            swap(m, n);
        }

        vector<bool> dp(n + 1, false);
        dp[n] = true;
        for (int i = m; i >= 0; i--) {
            bool nextDp = true;
            for (int j = n - 1; j >= 0; j--) {
                bool res = false;
                if (i < m && s1[i] == s3[i + j] && dp[j]) {
                    res = true;
                }
                if (j < n && s2[j] == s3[i + j] && nextDp) {
                    res = true;
                }
                dp[j] = res;
                nextDp = dp[j];
            }
        }
        return dp[0];
    }
};

Fixed code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        if (n < m) {
            swap(s1, s2);
            swap(m, n);
        }

        vector<bool> dp(n + 1, false);
        dp[n] = true;

        for (int i = m; i >= 0; --i) {
            // Update dp[n] for current i
            if (i < m) dp[n] = (s1[i] == s3[i + n] && dp[n]);

            bool nextDp = dp[n]; // this is dp[j+1] for j = n-1

            for (int j = n - 1; j >= 0; --j) {
                bool res = false;
                if (i < m && s1[i] == s3[i + j] && dp[j]) {
                    res = true; // take from s1
                }
                if (j < n && s2[j] == s3[i + j] && nextDp) {
                    res = true; // take from s2
                }
                dp[j] = res;
                nextDp = dp[j]; // for next iteration of j
            }
        }
        return dp[0];
    }
};

Whereas before, nextDp was assumed to be true before second loop but it is not true that s1 can always interleave with s3 at i + n; its possible that nothing in s1 interleaves