Straightforward C++ DP solution O(n^4)-time O(n^3)-space


  • 1

    This solution is based on a previous thread: https://leetcode.com/discuss/13258/my-o-n-4-solution-any-question

    The basic idea of this algorithm is to maintain a three-dimension array (henceforth called eq[N][N][N+1]), where (eq[first1][first2][len] == true) if and only if (s1[first1 ... first1+len-1] == s2[first2 ... first2+len-1]). In order to simplify the notation, we discard eq[-][-][0].

    Time complexity: O (n^4)

    Space complexity: O (n^3)

    class Solution {
    public:
    	bool isScramble(string s1, string s2) {
    		bool ret = true;
    		size_t n = s1.length();
    		if (n > 0) // if s1 is empty, return true
    		{
    			// Dynamic Programming: 
    			// eq[first1][first2][len] == true iff s1[first1 ... first1+len) == s2[first2 ... first2+len)
    			vector<vector<vector<bool> > > eq
    				(n, vector<vector<bool>>(n, vector<bool>(n + 1, false))); // initialize: all false
    
    			// initialize: eq[first1][first2][1] = true iff s1[first1] == s2[first2]
    		    for (int first1 = 0; first1 < n; ++first1)
    			{
    				for (int first2 = 0; first2 < n; ++first2)
    				{
    				    eq[first1][first2][1] = (s1[first1] == s2[first2]);
    				}
    			}
    
    			// dp: eq[first1][first2][len] = true iff two substrings are both matched.
    			for (size_t len = 2; len <= n; ++len)
    			{
    				for (size_t first1 = 0; first1 + len <= n; ++first1)
    				{
    					for (size_t first2 = 0; first2 + len <= n; ++first2)
    					{
    						for (size_t len1 = 1; len1 < len; ++len1)
    						{
    							size_t len2 = len - len1;
    
    							// two substrings are not swapped
    							if (eq[first1][first2][len1] && eq[first1 + len1][first2 + len1][len2])
    							{
    								eq[first1][first2][len] = true;
    							}
    
    							// two substrings are swapped
    							if (eq[first1][first2 + len2][len1] && eq[first1 + len1][first2][len2])
    							{
    								eq[first1][first2][len] = true;
    							}
    						}
    					}
    				}
    			}
    			ret = eq[0][0][n];
    		}
    		return ret;
    	}
    };

Log in to reply
 

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