LeetCode: Scramble String

这题看了网上答案

 1 class Solution {
 2 public:
 3     bool isScramble(string s1, string s2) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (s1.size() != s2.size()) return false;
 7         map<char, int> S1, S2;
 8         for (int i = 0; i < s1.size(); i++) S1[s1[i]]++;
 9         for (int i = 0; i < s2.size(); i++) S2[s2[i]]++;
10         if (S1 != S2) return false;
11         if (s1.size() == 1) return true;
12         for (int i = 1; i < s1.size(); i++) {
13             bool flag = isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, s1.size()-i), s2.substr(i, s2.size()-i));
14             flag = flag || (isScramble(s1.substr(0, i), s2.substr(s2.size()-i, i)) && isScramble(s1.substr(i, s1.size()-i), s2.substr(0, s2.size()-i)));
15             if (flag) return true;
16         }
17         return false;
18     }
19 };

三维DP更牛逼！

 1 class Solution {
 2 public:
 3     bool isScramble(string s1, string s2) {
 4         if (s1.size() != s2.size()) return false;
 5         int n = s1.size();
 6         vector<vector<vector<bool> > > f(n, vector<vector<bool> >(n, vector<bool>(n)));
 7         for (int i = 0; i < n; ++i) {
 8             for (int j = 0; j < n; ++j) {
 9                 f[i][j][0] = (s1[i] == s2[j]);
10             }
11         }
12         for (int l = 1; l < n; ++l) {
13             for (int i = 0; i+l < n; ++i) {
14                 for (int j = 0; j+l < n; ++j) {
15                     for (int k = 0; k < l; ++k) {
16                         f[i][j][l] = f[i][j][l] || (f[i][j][k] && f[i+k+1][j+k+1][l-1-k] || f[i][j+l-k][k] && f[i+k+1][j][l-1-k]);
17                     }
18                 }
19             }
20         }
21         return f[0][0][n-1];
22     }
23 };

 1 public class Solution {
 2     public bool IsScramble(string s1, string s2) {
 3         if (s1.Length != s2.Length) return false;
 4         Dictionary<char, int> S1 = new Dictionary<char, int>();
 5         Dictionary<char, int> S2 = new Dictionary<char, int>();
 6         for (int i = 0; i < s1.Length; i++) {
 7             if (S1.ContainsKey(s1[i])) S1[s1[i]]++;
 8             else S1.Add(s1[i], 1);
 9         }
10         for (int i = 0; i < s2.Length; i++) {
11             if (S2.ContainsKey(s2[i])) S2[s2[i]]++;
12             else S2.Add(s2[i], 1);
13         }
14         foreach (var v in S1) {
15             if (!S2.ContainsKey(v.Key) || v.Value != S2[v.Key]) return false;
16         }
17         if (s1.Length == 1) return true;
18         for (int i = 1; i < s1.Length; i++) {
19             bool flag = IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i, s1.Length-i), s2.Substring(i, s2.Length-i));
20             flag = flag || (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length-i, i)) && IsScramble(s1.Substring(i, s1.Length-i), s2.Substring(0, s2.Length-i)));
21             if (flag) return true;
22         }
23         return false;
24     }
25 }

View Code