C++ 8ms 20 lines clean solution


  • 0
    A
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int size1 = s1.size(), size2 = s2.size(), size3 = s3.size();
            if (size1 + size2 != size3) return false;
            vector<vector<bool>> dp(size1+1, vector<bool>(size2+1, false));
            dp[size1][size2] = true;
            for (int i = size2-1; i >= 0; --i){
                dp[size1][i] = dp[size1][i+1] == false ? false : s2[i] == s3[size1+i];
            }
            for (int i = size1-1; i >= 0; --i){
                dp[i][size2] = dp[i+1][size2] == false ? false : s1[i] == s3[i+size2];
            }        
            for (int i = size1 - 1; i>=0; --i){
                for (int j = size2 - 1; j >= 0; --j){
                    dp[i][j] = (s1[i] == s3[i+j] && dp[i+1][j]) || (s2[j] == s3[i+j] && dp[i][j+1]);
                }
            }
            return dp[0][0];
        }
    };

Log in to reply
 

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