My dp 8 ms C++ solution, 10 lines


  • 0
    S
        if (s1.size() + s2.size() != s3.size()) return false;
        vector<bool> v(s2.size() + 1, false);
        vector<vector<bool> > e(s1.size() + 1, v); 
        e[0][0] = true;
        
        for (int m = 0; m < s3.size(); m++)
            for (int i = max(m - s2.size(), 0); i <= min(m, s1.size()); i++) {
                int j = m - i;
                if (e[i][j] && i < s1.size() && s1[i] == s3[m]) {
                    e[i + 1][j] = true;
                }
                if (e[i][j] && j < s2.size() && s2[j] == s3[m]) {
                    e[i][j + 1] = true;
                }
            }
        return e[s1.size()][s2.size()];

Log in to reply
 

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