87. Scramble String

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

如果 s1 跟 s2 中出現 character 的頻率不一樣的話，回傳 false 即可。

如果一樣的話，那麼可以試著切切看。
對於 s1，如果切成 s1 = s1[1: i] + s1[i + 1: n]，長度爲 i 以及 n - i 的 substring，那麼 s2 可以切成 s2 = s2[1: i] + s2[i + 1: n] 或是 s2 = s2[1: n - i - 1] + s2[n - i: n]。
接著再比較兩組 substring 是否爲 scramble string 即可。

這邊可以用 unordered_map 來記錄算過的子問題，也可以用一般的矩陣來記錄。所以其實這題有點 recursion + dp 的感覺。

以下是沒有記錄子問題的 code，直接跑會 TLE。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool isScramble(string s1, string s2) {
    int freq[26] = {};
    int n = s1.size();
    
    if (n == 1){
        return s1 == s2;
    }
    
    for (int i = 0; i < n; i++){
        freq[s1[i] - 'a']++;
        freq[s2[i] - 'a']--;
    }
    
    for (int i = 0; i < 26; i++){
        if (freq[i] != 0){
            return false;
        }
    }
    
    for (int i = 1; i < n; i++){
        string s1_substring1 = s1.substr(0, i);
        string s1_substring2 = s1.substr(i);
        
        string s2_substring1 = s2.substr(0, i);
        string s2_substring2 = s2.substr(i);
        
        string s2_substring3 = s2.substr(0, n - i);
        string s2_substring4 = s2.substr(n - i);
        
        if (isScramble(s1_substring1, s2_substring1) && isScramble(s1_substring2, s2_substring2)){
            return true;
        }
        if (isScramble(s1_substring1, s2_substring4) && isScramble(s1_substring2, s2_substring3)){
            return true;
        }
    }
    return false;
}

加上 unordered_map 的方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
unordered_map<string, bool> mp;

bool isScramble(string s1, string s2) {
    if (mp.find(s1 + s2) != end(mp)){
        return mp[s1 + s2];
    }
    int freq[26] = {};
    int n = s1.size();
    
    if (n == 1){
        return s1 == s2;
    }
    
    for (int i = 0; i < n; i++){
        freq[s1[i] - 'a']++;
        freq[s2[i] - 'a']--;
    }
    
    for (int i = 0; i < 26; i++){
        if (freq[i] != 0){
            mp[s1 + s2] = false;
            return false;
        }
    }
    
    for (int i = 1; i < n; i++){
        string s1_substring1 = s1.substr(0, i);
        string s1_substring2 = s1.substr(i);
        
        string s2_substring1 = s2.substr(0, i);
        string s2_substring2 = s2.substr(i);
        
        string s2_substring3 = s2.substr(0, n - i);
        string s2_substring4 = s2.substr(n - i);
        
        if (isScramble(s1_substring1, s2_substring1) && isScramble(s1_substring2, s2_substring2)){
            mp[s1 + s2] = true;
            return true;
        }
        if (isScramble(s1_substring1, s2_substring4) && isScramble(s1_substring2, s2_substring3)){
            mp[s1 + s2] = true;
            return true;
        }
    }
    mp[s1 + s2] = false;
    return false;
}

用矩陣記錄的方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool isScramble(string s1, string s2) {
    int n = s1.size();
    vector<vector<vector<int>>> memo(n, vector<vector<int>> (n, vector<int> (n + 1, -1)));
    function<int(int, int, int)> dp = [&](int start_1, int start_2, int length){
        if (length == 1){
            return s1[start_1] == s2[start_2]? 1: 0;
        }
        if (memo[start_1][start_2][length] != -1){
            return memo[start_1][start_2][length];
        }
        
        int freq[26] = {};
        for (int i = 0; i < length; i++){
            freq[s1[start_1 + i] - 'a']++;
            freq[s2[start_2 + i] - 'a']--;
        }
        for (int i = 0; i < 26; i++){
            if (freq[i] != 0){
                memo[start_1][start_2][length] = 0;
                return 0;
            }
        }
        
        for (int i = 1; i < length; i++){
            if (dp(start_1, start_2, i) == 1 && dp(start_1 + i, start_2 + i, length - i) == 1){
                memo[start_1][start_2][i] = 1;
                return 1;
            }
            if (dp(start_1, start_2 + length - i, i) == 1 && dp(start_1 + i, start_2, length - i) == 1){
                memo[start_1][start_2][i] = 1;
                return 1;
            }
        }
        memo[start_1][start_2][length] = 0;
        return 0;
    };
    return dp(0, 0, n) == 1;
}

memo[start_1][start_2][length] 代表的是「s1[start_1: start_1 + length - 1] 以及 s2[start_2: start_2 + length - 1] 是否爲 scramble string」。

至於這題的複雜度有點難分析。在不做 dp 的情況下，時間複雜度會是 $O(5^n)$

$$ \begin{align*} T(n) &= 2((T(1) + T(n - 1)) + (T(2) + T(n - 2)) + … + (T(n - 1) + T(1)))\\ &= 4(T(1) + T(2) + … + T(n - 1))\\ &= 4T(n - 1) + 4(T(1) + T(2) + … + T(n))\\ &= 4T(n - 1) + T(n - 1)\\ &= 5T(n - 1)\\ &= O(5^n) \end{align*} $$

如果使用矩陣來記錄，那麼時間複雜度會是 $O(n^4)$。
有 $O(n^3)$ 個格子要填，而每填一個格子需要 $O(n)$ 的時間。

如果用 unordered_map 來記錄，時間複雜度「應該」也會是 $O(n^4)$。
這邊比較不確定的地方是，用 string 當作 key 時，unordered_map 其實並不是 $O(1)$，而是 $O(n)$，因此不太確定複雜度會不會提高。