Rolling Arrays C++ implementation


  • 0
    F
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
            if (len1 + len2 != len3) return false;
            if (len1 == 0) return s2 == s3;
            if (len2 == 0) return s1 == s3;
            vector<vector<bool>> dp(2, vector<bool>(len2 + 1, false));
            dp[0][0] = true;
            //for (int i = 1; i <= len1; i++) dp[i][0] = (s1[i-1]==s3[i-1] && dp[i-1][0]);
            //for (int i = 1; i <= len2; i++) dp[0][i] = (s2[i-1]==s3[i-1] && dp[0][i-1]);
            for (int i = 0; i <= len1; i++) {
                for (int j = 0; j <= len2; j++) {
                    if (i == 0 && j > 0) {
                        dp[0][j] = (s2[j-1]==s3[j-1] && dp[0][j-1]);
                    }
                    if (j == 0 && i > 0) {
                        dp[i&1][0] = (s1[i-1]==s3[i-1] && dp[(i-1)&1][0]);
                    }
                    if (i > 0 && j > 0) {
                        dp[i&1][j] = (s3[i + j - 1] == s1[i-1] && dp[(i-1)&1][j]) ||
                                (s3[i + j - 1] == s2[j-1] && dp[i&1][j-1]);
                    }
                }
            }
            return dp[len1&1][len2];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.