Leetcode 87 Solution

This article provides solution to leetcode question 87 (scramble-string)
Categories:
Tags:
Access this page by simply typing in "lcs 87" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/scramble-string

Solution

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;

        int n = s1.size();
        if (n == 0)
            return true;

        if (s1 == s2)
            return true;

        auto t1 = s1;
        auto t2 = s2;
        sort(t1.begin(), t1.end());
        sort(t2.begin(), t2.end());

        if (t1 != t2)
            return false;

        for (int i = 1; i < n; i++)
        {
            auto s11 = s1.substr(0, i);
            auto s12 = s1.substr(i);

            auto s21 = s2.substr(0, i);
            auto s22 = s2.substr(i);
            auto s23 = s2.substr(0, n - i);
            auto s24 = s2.substr(n - i);

            if (isScramble(s11, s21) && isScramble(s12, s22))
                return true;

            if (isScramble(s11, s24) && isScramble(s12, s23))
                return true;
        }

        return false;
    }
};