0 ms c++ DP solution


  • 0
    H

    DP formula:

    f(s1,s2,s3) = (s1[0]==s3[0] && f(s1.substr(1), s2, s3.substr(1))) ||  (s2[0]==s3[0] && f(s1, s2.substr(1), s3.substr(1)))
    
    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int m = s1.size();
            int n = s2.size();
            vector<vector<int>> res(m+1, vector<int>(n+1, -1));
            helper(res, s1, 0, s2, 0, s3);
            return res[0][0] == 1;
        }
        
        bool helper(vector<vector<int>>& res, string& s1, int i, string& s2, int j, string& s3) {
            int x = s1.size() - i;
            int y = s2.size() - j;
            int z = s3.size() - i - j;
            if (x+y != z) {
                res[i][j] = 0;
            }
            else {
                if (x == 0 && y == 0) res[i][j] = 1;
                else if (x == 0) res[i][j] = s2.substr(j) == s3.substr(i+j) ? 1 : 0;
                else if (y == 0) res[i][j] = s1.substr(i) == s3.substr(i+j) ? 1 : 0;
            }
            if (res[i][j] >= 0) return res[i][j];
            bool r1 = false, r2 = false;
            if (s1[i] == s3[i+j]) r1 = helper(res, s1, i+1, s2, j, s3); 
            if (s2[j] == s3[i+j]) r2 = helper(res, s1, i, s2, j+1, s3);
            res[i][j] = (r1 || r2) ? 1 : 0;
            return res[i][j];
        }
    };
    

Log in to reply
 

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