My c++ DP solution with O(min(m, n)) extra space


  • 0
    Q
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
            
            vector<int> A(s1.size() + 1, 1);
            
            for(int i = 1; i < A.size(); i++)
            {
                A[i] = s1[i - 1] == s3[i - 1] ? A[i - 1] : 0;
            }
            
            for(int j = 1; j <= s2.size(); j++)
            {
                 A[0] = s2[j - 1] == s3[j - 1] ? A[0] : 0; 
                for(int i = 1; i <= s1.size(); i++)
                {
                   if(s1[i - 1] == s3[i + j - 1] && s2[j - 1] != s3[i + j -1])  A[i] = A[i -1] ;
                   else if(s1[i - 1] != s3[i + j - 1] && s2[j - 1] == s3[i + j -1]) ;
                   else if(s1[i - 1] == s3[i + j - 1] && s2[j - 1] == s3[i + j -1]) A[i] = A[i] || A[i - 1];
                   else A[i] = 0;
                }
            }
            return A.back();
        }
    

Log in to reply
 

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