Accepted 6ms DP solution, similar with what is used in Regular Expression Matching.


  • 0

    Here is my accepted c++ DP solution, 6ms:

    class Solution {
    public:
        bool isInterleave(std::string s1, std::string s2, std::string s3) {
    		if (s1.empty())
    			return s2 == s3;
    		if (s2.empty())
    			return s1 == s3;
    		int len1 = static_cast<int>(s1.size()), len2 = static_cast<int>(s2.size()), len3 = static_cast<int>(s3.size());
    		if (len1 + len2 != len3)
    			return false;
    		std::vector<std::vector<int> > flag(len1 + 1, std::vector<int>(len2 + 1));
    		flag[0][0] = 1;
    		for (int i = 1; i <= len2; ++i)
    			flag[0][i] = flag[0][i - 1] && s2[i - 1] == s3[i - 1];
    		for (int i = 1; i <= len1; ++i) {
    			flag[i][0] = flag[i - 1][0] && s1[i - 1] == s3[i - 1];
    			for (int j = 1; j <= len2; ++j) {
    				flag[i][j] = flag[i - 1][j] && s3[i + j - 1] == s1[i - 1] || 
    					flag[i][j - 1] && s3[i + j - 1] == s2[j - 1];
    			}
    		}
    		return flag[len1][len2];
    	}
    };
    

    The similar question is Regular Expression Matching, and here is the solution:

    class Solution {
    public:
        bool isMatch(std::string s, std::string p) {
            std::vector<std::vector<int> > f(s.size() + 1, std::vector<int>(p.size() + 1));
            f[0][0] = 1;
    		for (int i = 2; i <= p.size(); ++i)
                f[0][i] = p[i - 1] == '*' && f[0][i - 2];
    		for (int i = 1; i <= s.size(); ++i)
    			for (int j = 1; j <= p.size(); ++j)
    				 f[i][j] = p[j - 1] == '*' ? 
    					 f[i][j - 2] || f[i - 1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.') :
    					 f[i - 1][j - 1] && (p[j - 1] == s[i - 1] || p[j - 1] == '.');
    		return f[s.size()][p.size()];
        }
    };
    

Log in to reply
 

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