LeetCode 87. Scramble String [Hard] [C++] 解題筆記

這題給定兩個長度相等的的字串 s1, s2，要我們判斷 s1 是不是 s2 的 scrambled string，所謂 scrambled string 是指說將 string 用 binary tree 的方式切割，若透過 swap 某些 non-leaf node 的兩個子節點的位置可以使 s1 變成 s2 的話就說 s1 is a scrambled string of s2.

EX:

     s1:                                 

    great                
   /        \
 gr       eat
 / \        /  \
g  r     e   at
          / \
        a   t

    s2:

    rgeat
   /        \
 rg       eat
 / \        /  \
r   g    e   at
          / \
        a   t

Ans: True,  可以透過交換 s1 中 gr 的兩個子節點來將 s1 轉成 s2。

想法:

    這題可以用遞迴的方式來做，遞迴去看 s1 和 s2 的 substring 之間是否相等，若兩個字串相等表示

不用 swap 兩者本來就是相同的，因此子問題可以分為有 swap 和 不 swap 來分別遞歸求解，

然後依位置(length 1 ~ length s1.size()做切割再照上述兩種方向做遞歸求解即可。另外這邊必須做一個剪枝

不然會超時，可以發現如果當前的子串所包含的字元不一樣的話就一定會 fail 可以不用繼續遞歸。

                                             f(great, rgeat)

                                non swap       /  \     swap  

                       f(g,r) && f(reat, reat)   f(r,r) && f(geat,geat)

完整程式碼:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        const int l = s1.length();
        if (s1 == s2) { return true; }
        if (freq(s1) != freq(s2)) { return false; }
        for (int i = 1; i < l; i++) {
            // partition on i and not swap
            if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
                isScramble(s1.substr(i), s2.substr(i)) ||
                // partition on i and swap s2
                isScramble(s1.substr(0, i), s2.substr(l - i, i)) &&
                isScramble(s1.substr(i), s2.substr(0, l - i))) {
                
                return true;
            }
        }
        return false;
    }
private:
    vector<int> freq(string_view s) {
        vector<int> f(26);
        for (auto c : s) {
            ++f[c - 'a'];
        }
        return f;
    }
};