87.Scramble String

tags: Hard,String,DP

87. Scramble String

題目描述

We can scramble a string s to get a string t using the following algorithm:

If the length of the string is 1, stop.
If the length of the string is > 1, do the following:

• Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
• Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
• Apply step 1 recursively on each of the two substrings x and y.

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

範例

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Example 3:

Input: s1 = "a", s2 = "a"
Output: true

Constraints:

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1 and s2 consist of lowercase English letters.

解答

C++

思路:

1. 題目為s1及s2經過以下操作後是否相同
   1.1 隨機切割成兩個substring
   1.2 此兩個substring可以交換或不交換
   1.3 重複上述兩步把字串都分割成size為1的substring
2. 暴力作法把s1去切每一組substring, 每一組比較以下兩種
   2.1 substring不交換跟s2對應的位置比
   2.2 substring交換後跟s2對應的位置比
3. 切到最後substring只剩一個字符或是相同的兩個字符, 故基本return判別為比較兩組字串

喜得TLE

class Solution {
public:
    bool DFS(string s1, string s2)
    {
        if(s1==s2)
            return true;        
        bool res = false;
        int n = s1.size();
        for(int i = 1; i < n && !res; i++)
        {
            res |= (DFS(s1.substr(0, i), s2.substr(0, i)) && DFS(s1.substr(i), s2.substr(i)));
            res |= (DFS(s1.substr(0, i), s2.substr(n-i, i)) && DFS(s1.substr(i), s2.substr(0, n-i)));
        }
        return res;        
    }

    bool isScramble(string s1, string s2) {
        return DFS(s1, s2);
    }
};

4. 用hash儲存已經做過的substring pair, 因為輸入s1與s2大小一致, 在後續切割時也都切割同樣大小的size, 紀錄pair時直接s1+s2作為key即可

class Solution {
public:
    bool DFS(string s1, string s2, unordered_map<string, bool>& m)
    {
        if(s1==s2)
            return true;
        if(m.count(s1+s2))
            return m[s1+s2];
        
        bool res = false;
        int n = s1.size();
        for(int i = 1; i < n && !res; i++)
        {
            res |= (DFS(s1.substr(0, i), s2.substr(0, i), m) && DFS(s1.substr(i), s2.substr(i), m));
            res |= (DFS(s1.substr(0, i), s2.substr(n-i, i), m) && DFS(s1.substr(i), s2.substr(0, n-i), m));
        }
        m[s1+s2] = res;
        return res;        
    }

    bool isScramble(string s1, string s2) {
        unordered_map<string, bool> m;
        return DFS(s1, s2, m);
    }
};

Time:

$O(n^4)$(?) 從一開始到切到最小有n…1種切法(n^2), 每個切法去比較s1每個位置跟s2的每個位置是否相符(n^2)
Extra Space:

$O(n^4)$

Follow up:

1. 可以用字串頻率加速

XD March 31, 2023

Reference

回到題目列表