3ms, C++ solution, DP


  • 0
    Z
    class Solution {
    public:
    	bool isInterleave(string s1, string s2, string s3) {
    		if (s3.size() != (s1.size() + s2.size()))
    		{
    			return false;
    		}
    
    		if (s1.empty() && (s2 == s3) || s2.empty() && (s1 == s3))
    		{
    			return true;
    		}
    
    		if (s1.empty() && (s2 != s3) || s2.empty() && (s1 != s3))
    		{
    			return false;
    		}
    
    		int total = (s1.size() + 1) * (s2.size() + 1);
    		vector<int> vec(total, 0);
    		vec[total - 1] = 1;
    		return isInterleave(s1, s2, s3, 0, 0, vec) == 1;
    	}
    
    	int isInterleave(const string & s1, const string & s2, const string & s3,
    		int s1Index, int s2Index, vector<int> & vec)
    	{
    		if (vec[s2Index * (s1.size() + 1) + s1Index] != 0)
    		{
    			return vec[s2Index * (s1.size() + 1) + s1Index];
    		}
    
    		if (s1Index == s1.size() || s1[s1Index] != s3[s1Index + s2Index])
    		{
    			if (s2[s2Index] != s3[s1Index + s2Index])
    			{
    				vec[s2Index * (s1.size() + 1) + s1Index] = -1;
    			}
    			else
    			{
    				vec[s2Index * (s1.size() + 1) + s1Index] = isInterleave(s1, s2, s3, s1Index, s2Index + 1, vec);
    			}
    		}
    		else if (s2Index == s2.size() || s2[s2Index] != s3[s1Index + s2Index])
    		{
    			if (s1[s1Index] != s3[s1Index + s2Index])
    			{
    				vec[s2Index * (s1.size() + 1) + s1Index] = -1;
    			}
    			else
    			{
    				vec[s2Index * (s1.size() + 1) + s1Index] = isInterleave(s1, s2, s3, s1Index + 1, s2Index, vec);
    			}
    		}
    		else
    		{
    			int val1 = isInterleave(s1, s2, s3, s1Index, s2Index + 1, vec);
    			int val2 = isInterleave(s1, s2, s3, s1Index + 1, s2Index, vec);
    			vec[s2Index * (s1.size() + 1) + s1Index] = (val1 + val2 != -2 ? 1 : -1);
    		}
    
    		return vec[s2Index * (s1.size() + 1) + s1Index];
    	}
    };

Log in to reply
 

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