C++, DFS+DP solution, 0ms


  • 0
    H
    class Solution {
    public:
    bool **p;
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size()+s2.size() != s3.size()) return false;
        if(s3.size() == 0) return true;
        if(s1.size() == 0) return s2==s3;
        if(s2.size() == 0) return s1==s3;
        p = new bool*[s1.size()+1];
        for(int i = 0; i < s1.size()+1; i++){
            p[i] = new bool[s2.size()+1];
            for(int j = 0; j < s2.size()+1; j++) p[i][j] = true;
        }  
        return dfs(s1, 0, s2, 0, s3, 0);
    }
    bool dfs(string &s1, int a, string &s2, int b, string &s3, int step){
        if(step >= s3.size()) return true;
        if(a<s1.size()){
            if(p[a][b] && s1[a] == s3[step] && dfs(s1, a+1, s2, b, s3, step+1)){
             return true;
          }
        }
        if(b<s2.size()){
             if(p[a][b] && s2[b] == s3[step] && dfs(s1, a, s2, b+1, s3, step+1)){
                return true;
            }
        }
        p[a][b] = false;
        return false;
      }
    };

Log in to reply
 

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