3ms C++ solution using Backtrack, easy to implement, you'd like it


  • 0
    L

    It seems every one is using DFS/BFS/DP, but I found Backtrack is also useful for this problem
    so here is my solution, using backTrace you don't have to handle queue or array manually,
    I think it's more practical in interview

    class Solution {
    public:
        map<pair<int,int>,bool> visited;
        bool backTrack(string &s1, string &s2, string &s3,int step,int i,int j)
        {
            if ( visited.find(make_pair(i,j)) != visited.end())
                return false;
            if ( step == s3.size() )
                return true;
            if ( i < s1.size() && s1[i] == s3[step] && backTrack(s1,s2,s3,step+1,i+1,j))
                return true;
            if ( j < s2.size() && s2[j] == s3[step] && backTrack(s1,s2,s3,step+1,i,j+1))
                return true;
            visited[make_pair(i,j)] = true;
            return false;
        }
        
        bool isInterleave(string s1, string s2, string s3) {
            if ( s1.size() + s2.size() != s3.size() )   return false;
            return backTrack(s1,s2,s3,0,0,0);
        }
    };
    

Log in to reply
 

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