C++ 6 lines, O(mn) Time O(n) Space DP 4ms


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

Log in to reply
 

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