C++ solutions w/ explanation. Both recursive and Top-Down Dynamic Programming.


  • 7
    C
    // This was a very interesting problem! Here is my solution, using top down dynamic programming. 
    //
    // Lets discuss the recurrence. The question posed is, when is string s1 considered to be a scrambling of string s2? 
    // Let us pose this as a modified question in the form of the following boolean function:
    // bool isScrambling(int s1s, int s1e, int s2s, int s2e);
    // i.e., given two strings s1 and s2, are their SUBSTRINGS s1[s1s, s1e] and s2[s2s, s2e] scramblings of each other?
    // The original question can be answered by isScrambling(0, s1.length()-1, 0, s2.length() -1);
    //
    //    First the trivial cases which result in false result:
    //     1. The two strings are not of same length, then it cannot be a scrambling.
    //     2. if s1e < s1s, or s2e < s2s, then they are not scramblings of each other.
    //
    //    Now the case for identity scrambling (i.e. no scrambling at all)
    //    If s1[s1s, s1e] == s2[s2s, s2e] then they are trivial scramblings of each other
    //
    //    Another trivial case, if the two strings are of length 1, just check that character
    //    
    //    Now we come to the meat of the problem. Consider all breaks of the string s1:
    //    s1[s1s, s1s+k] and s1[s1s+k+1, s1e] for all k <-[0..(s1e-s1s)]
    //       for each of these substrings, the original strings are scramblings if
    //       1. Either isScrambling(s1s, s1s+k, s2s, s2s+k)   && isScrambling(s1s+k+1, s1e, s2s+k+1, s2e)
    //       2. Or isScrambling(s1s, s1s+k, (s2e-k), s2e)     && isScrambling(s1s+k+1, s1e, s2s, s2e-k-1)
    //     The first case is one where we do NOT flip the current node in the tree.
    //     The second case is one where we flip the current node in the tree.
    //
    //    If none of the above cases return true, then the strings are NOT scramblings of each other.
    //
    // Here is a non-memoized (hence non-DP) recursive version:
    class Solution {
        string s1;
        string s2;
    public:
        // is s1[s1s, s1e] a scrambling of s2[s2s, s2e]?
        bool isScrambling (int s1s, int s1e, int s2s, int s2e) {
            if ((s1e-s1s) != (s2e-s2s)) return false;
            if (s1e < s1s || s2e < s2s) return false;
            if (s1.substr(s1s, (s1e - s1s + 1)) == s2.substr(s2s, (s2e - s2s + 1))) return true; //identity scrambling
            if (s1e == s1s) return s1[s1s] == s2[s2s];     
            for (int k=0; k<(s1e-s1s); k++) { 
                if (isScrambling(s1s, s1s+k, s2s, s2s+k)   && isScrambling(s1s+k+1, s1e, s2s+k+1, s2e)) return true;
                if (isScrambling(s1s, s1s+k, (s2e-k), s2e) && isScrambling(s1s+k+1, s1e, s2s, s2e-k-1)) return true;
            }
            return false;
        }
        bool isScramble(string is1, string is2) {
            if (is1.length() == 0 || is2.length() == 0) return false;
            s1 = is1;
            s2 = is2;
            return isScrambling(0, s1.length()-1, 0, s2.length()-1);
        }
    };
    // The above solution is functionally correct, but will result in Time-Limit-Exceeded, 
    // because we are solving the same sub-problems again and again and again
    //
    // To make this dynamic programming, we just have to memoize the results. 
    // i.e. first check if results are in the cache, if so return them
    // else compute the results, store in cache, and return the result.
    // Here is a Top-Down dynamic programming version, which now passes in the online judge:
    //
    class Solution {
        string s1;
        string s2;
        std::hash<std::string> str_hash;
        unordered_map<size_t, bool> cache;
        
        // is s1[s1s, s1e] a scrambling of s2[s2s, s2e]?
        bool isScrambling (int s1s, int s1e, int s2s, int s2e) {
            string hashStr = s1.substr(s1s, s1e-s1s+1) + "#" + s2.substr(s2s, s2e-s2s+1);
            auto it = cache.find(str_hash(hashStr));
            if (it != cache.end()) { 
                return it->second;
            }
            bool ret = false;
            if ((s1e-s1s) != (s2e-s2s)) {ret = false;}
            else if (s1e < s1s || s2e < s2s) {ret = false;}
            else if (s1.substr(s1s, (s1e - s1s + 1)) == s2.substr(s2s, (s2e - s2s + 1)))  { ret = true;} //identity scrambling
            else if (s1e == s1s) {ret = s1[s1s] == s2[s2s];}      
            else {
                for (int k=0; k<(s1e-s1s); k++) { 
                    if (isScrambling(s1s, s1s+k, s2s, s2s+k)   && isScrambling(s1s+k+1, s1e, s2s+k+1, s2e)) {ret = true; break;}
                    if (isScrambling(s1s, s1s+k, (s2e-k), s2e) && isScrambling(s1s+k+1, s1e, s2s, s2e-k-1)) {ret = true; break;}
                }
            }
            cache[str_hash(hashStr)] = ret;
            return ret;
        }
    public:
        bool isScramble(string is1, string is2) {
            if (is1.length() == 0 || is2.length() == 0) return false;
            s1 = is1;
            s2 = is2;
            return isScrambling(0, s1.length()-1, 0, s2.length()-1);
        }
    

    };


Log in to reply
 

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