3 ms DP solution with 2D array


  • 0
    J
    class Solution {
    public:
        
        bool isInterleave(string s1, string s2, string s3) 
        {
            if (s1.length() + s2.length() != s3.length()) return false;
           
            vector<vector<char>> matrix;
            for (int i=0; i<=s2.length(); ++i)
                matrix.push_back(vector<char>(s1.length()+1, 0));
            matrix[0][0] = 1;
            
            for (int k=0; k<s3.length(); ++k) {
                char c3 = s3[k];
                int j = k+1 > s1.length() ? s1.length() : k+1;
                int i = j == k+1 ? 0 : k+1 - j;
                
                char match = 0;
                for (int t = 0; t<=s2.length()-i; ++t) {
                    int x = j-t, y = i+t;
                    if (y > 0) matrix[y][x] |= matrix[y-1][x] & (s2[y-1] == c3 ? 1 : 0);
                    if (x > 0) matrix[y][x] |= matrix[y][x-1] & (s1[x-1] == c3 ? 1 : 0);
                    match |= matrix[y][x];
                }
                if (match == 0) return false;
            }
            
            return matrix[s2.length()][s1.length()] == 1;
        }
    };
    

Log in to reply
 

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