C++ DP with O(n) space and 6 lines of core logic code


  • 0
    H
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) {
            return false;
        }
    
        vector<bool> dp(s2.size()+1, false);
        for (int i = s1.size(); i >= 0; --i) {
            for (int j = s2.size(); j >= 0; --j) {
                dp[j] = (i == s1.size() && j == s2.size()) ||
                        (i < s1.size() && s1[i] == s3[i+j] && dp[j]) ||
                        (j < s2.size() && s2[j] == s3[i+j] && dp[j+1]);
            }
        }    
    
        return dp[0];
    }
    

Log in to reply
 

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