且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

[LeetCode] Scramble String

更新时间:2022-07-06 19:15:36

To solve this problem, you first need to understand it well. The key problem is tell the difference of  scramble from permutations. You may refer to this link for some nice discussions. Then you can proceed to solve it. This link posts a very easy and also very fast code, which is very readable. I almost copy it below.

 1 class Solution {
 2 public:
 3     bool isScramble(string s1, string s2) {
 4         if (s1 == s2) return true;
 5         int n = s1.length();
 6         int counts[26] = {0};
 7         for (int i = 0; i < n; i++) {
 8             counts[s1[i] - 'a']++;
 9             counts[s2[i] - 'a']--;
10         }
11         for (int i = 0; i < 26; i++)
12             if (counts[i]) return false;
13         for (int i = 1; i < n; i++) {
14             if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)))
15                 return true;
16             if (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))
17                 return true;
18         }
19         return false;
20     }
21 };