Recursive DP. 0ms. Clean and easy. 9 Lines :D


  • 0
    P

    EDIT : Fixed it! First solution is not TLE, second is. If someone is new to this like me, it will help spotting the difference.
    Just cache whatever path fails and never go down with it.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            vector<vector<bool>> valid(s1.size() + 1, vector<bool>(s2.size() + 1, true));
            if(s1.size() + s2.size() != s3.size()) return false;
            return canChoose(s1, s2, s3, s1.size(), s2.size(), s3.size(), valid);
        }
        
        bool canChoose(string &s1, string &s2, string &s3, int pos1, int pos2, int pos3, vector<vector<bool>> &valid)
        {
            if(pos1 == pos2 == pos1 == pos3) return true;
            if(!valid[pos1][pos2]) return false;
            if(pos1 > 0 && s1[pos1 - 1] == s3[pos3 - 1] && canChoose(s1, s2, s3, pos1 - 1, pos2, pos3 - 1, valid) ||
               pos2 > 0 && s2[pos2 - 1] == s3[pos3 - 1] && canChoose(s1, s2, s3, pos1, pos2 - 1, pos3 - 1, valid))
            valid[pos1][pos2] = true;
            else valid[pos1][pos2] = false;
            return valid[pos1][pos2];
        }
    };
    
    

    Was getting TLE. then decided to save for failed cases rather than the passing ones. More cases would fail anyway.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            vector<vector<bool>> valid(s1.size() + 1, vector<bool>(s2.size() + 1, false));
            if(s1.size() + s2.size() != s3.size()) return false;
            return canChoose(s1, s2, s3, s1.size(), s2.size(), s3.size(), valid);
        }
        
        bool canChoose(string &s1, string &s2, string &s3, int pos1, int pos2, int pos3, vector<vector<bool>> &valid)
        {
            if(pos1 == pos2 == pos1 == pos3) return true;
            if(valid[pos1][pos2]) return true;
            if(pos1 > 0 && s1[pos1 - 1] == s3[pos3 - 1] && canChoose(s1, s2, s3, pos1 - 1, pos2, pos3 - 1, valid) ||
               pos2 > 0 && s2[pos2 - 1] == s3[pos3 - 1] && canChoose(s1, s2, s3, pos1, pos2 - 1, pos3 - 1, valid))
            valid[pos1][pos2] = true;
            return valid[pos1][pos2];
        }
    };

Log in to reply
 

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