3ms DFS easy to understand


  • 4
    Y
    void isInterleave1(int i, int j, int k, string s1, string s2, string s3, bool &flag, vector<bool> &visit)
    {
    if (!flag)
    {
    	if (k == s3.length())
    	{
    		flag = true;
    		return;
    	}
    	if (!visit[i*(s2.length()+1) + j])
    	{
    		visit[i*(s2.length() + 1) + j] = true;
    		if (i < s1.length() && s3[k] == s1[i])
    		{
    			isInterleave1(i + 1, j, k + 1, s1, s2, s3, flag, visit);
    		}
    		if (j < s2.length() && s3[k] == s2[j])
    		{
    			isInterleave1(i, j + 1, k + 1, s1, s2, s3, flag, visit);
    		}
    	}
    }
    
    }
    bool isInterleave(string s1, string s2, string s3) {
    bool flag = false;
    if (s1.length() + s2.length() != s3.length())
    	return false;
    vector<bool> visit((s1.length()+1)*(s2.length()+1), false);
    isInterleave1(0, 0, 0, s1, s2, s3, flag, visit);
    return flag;
    }

Log in to reply
 

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