A 4 ms C++ solution, DP


  • 0

    For example: s1="ab", s2="cd" ,s3="acdb"
    Initialized matrix: mp[][]

    ? _ c d
    _ 1 0 0
    a 0 0 0
    b 0 0 0
    

    To the grid mp[i][j], if it's above grid or left grid is '1', look for whether it's represent letter (to mp[0][1], when it's left grid is 1, it's represent letter is 'c' now) == s3[i+j-1]. If true, change this grid into 1.

    bool isInterleave(string s1, string s2, string s3) 
    {
    	if (s3.size() != (s1.size() + s2.size()))
    		return 0;
    	int nrow = s1.size();
    	int ncol = s2.size();
    	vector<int> v(ncol + 1, 0);
    	vector<vector<int>> mp(nrow + 1, v);
    	mp[0][0] = 1;
    	int i, j;
    	for (i = 0; i <= nrow; ++i)
    	{
    		for (j = 0; j <= ncol; ++j)
    		{
    			if (i>0 && mp[i - 1][j])
    			{
    				if (s1[i - 1] == s3[i + j - 1])
    					mp[i][j] = 1;
    			}
    			if (j>0 && mp[i][j - 1])
    			{
    				if (s2[j - 1] == s3[i + j - 1])
    					mp[i][j] = 1;
    			}
    		}
    	}
    	return mp[nrow][ncol];
    }
    

    It's looks like also can use BFS to solve this problem for when mp[i][j]=1, extend it's right and below grid check whether the grid's represent letter == s3[i+j].


Log in to reply
 

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