Clean C++ DP solution


  • 2
    S
    class Solution {
    public:
      
        bool isInterleave(string s1, string s2, string s3) {
            int n = s1.size();
            int m = s2.size();
            int k = s3.size();
            
            if (k != n+m) return false;
            
            if (s1.empty()) return s2==s3;
            if (s2.empty()) return s1 == s3;
            
            vector<vector<bool>> t(n+1, vector<bool>(m+1, false));
            
            for (int i=0; i<=n; i++) {
                for (int j=0; j<=m; j++) {
                    if (i==0 && j==0) {
                        t[0][0] = true;
                    } 
                    
                    else if (i==0 && s2[j-1] == s3[j-1]) {
                        t[0][j] = t[0][j-1];
                    } 
                    
                    else if (j==0 && s1[i-1] == s3[i-1]) {
                        t[i][0] = t[i-1][0];
                    } 
                    
                    else if (i>0 && s1[i-1] == s3[i+j-1] && t[i-1][j]) {
                        t[i][j] = true;
                    } 
                    
                    else if (j>0 && s2[j-1] == s3[i+j-1] && t[i][j-1]) {
                        t[i][j] = true;
                    }
                }
            }
            
            return t[n][m];
        }
    };

  • 0
    W

    In fact You don't need following lines, right?

    if (i==0 && s2[j-1] == s3[j-1]) { t[0][j] = t[0][j-1]; } else if (j==0 && s1[i-1] == s3[i-1]) { t[i][0] = t[i-1][0]; }


Log in to reply
 

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