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

  • 0

    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 {
        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.