Scramble String

描述

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

  1.     great
  2.    /    \
  3.   gr    eat
  4.  / \    /  \
  5. g   r  e   at
  6.            / \
  7.           a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

  1.     rgeat
  2.    /    \
  3.   rg    eat
  4.  / \    /  \
  5. r   g  e   at
  6.            / \
  7.           a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

  1.     rgtae
  2.    /    \
  3.   rg    tae
  4.  / \    /  \
  5. r   g  ta  e
  6.        / \
  7.       t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

分析

首先想到的是递归（即深搜），对两个string进行分割，然后比较四对字符串。代码虽然简单，但是复杂度比较高。有两种加速策略，一种是剪枝，提前返回；一种是加缓存，缓存中间结果，即memorization（翻译为记忆化搜索）。

剪枝可以五花八门，要充分观察，充分利用信息，找到能让节点提前返回的条件。例如，判断两个字符串是否互为scamble，至少要求每个字符在两个字符串中出现的次数要相等，如果不相等则返回false。

加缓存，可以用数组或HashMap。本题维数较高，用HashMap，map和unordered_map均可。

既然可以用记忆化搜索，这题也一定可以用动规。设状态为f[n][i][j]，表示长度为n，起点为s1[i]和起点为s2[j]两个字符串是否互为scramble，则状态转移方程为

  1. f[n][i][j]} =  (f[k][i][j] && f[n-k][i+k][j+k]) 
  2.             || (f[k][i][j+n-k] && f[n-k][i+k][j])

递归

  1. // Scramble String
  2. // 递归，会超时，仅用来帮助理解
  3. // 时间复杂度O(n^6)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     bool isScramble(const string& s1, const string& s2) {
  7.         return isScramble(s1.begin(), s1.end(), s2.begin());
  8.     }
  9. private:
  10.     typedef string::iterator Iterator;
  11.     bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
  12.         auto length = distance(first1, last1);
  13.         auto last2 = next(first2, length);
  15.         if (length == 1) return *first1 == *first2;
  17.         for (int i = 1; i < length; ++i)
  18.             if ((isScramble(first1, first1 + i, first2)
  19.                  && isScramble(first1 + i, last1, first2 + i))
  20.                     || (isScramble(first1, first1 + i, last2 - i)
  21.                             && isScramble(first1 + i, last1, first2)))
  22.                 return true;
  24.         return false;
  25.     }
  26. };

动规

  1. // Scramble String
  2. // 动规，时间复杂度O(n^3)，空间复杂度O(n^3)
  3. class Solution {
  4. public:
  5.     bool isScramble(const string& s1, const string& s2) {
  6.         const int N = s1.size();
  7.         if (N != s2.size()) return false;
  9.         // f[n][i][j]，表示长度为n，起点为s1[i]和
  10.         // 起点为s2[j]两个字符串是否互为scramble
  11.         bool f[N + 1][N][N];
  12.         fill_n(&f[0][0][0], (N + 1) * N * N, false);
  14.         for (int i = 0; i < N; i++)
  15.             for (int j = 0; j < N; j++)
  16.                 f[1][i][j] = s1[i] == s2[j];
  18.         for (int n = 1; n

递归+剪枝

  1. // Scramble String
  2. // 递归+剪枝
  3. // 时间复杂度O(n^6)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     bool isScramble(const string& s1, const string& s2) {
  7.         return isScramble(s1.begin(), s1.end(), s2.begin());
  8.     }
  9. private:
  10.     typedef string::const_iterator Iterator;
  11.     bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
  12.         auto length = distance(first1, last1);
  13.         auto last2 = next(first2, length);
  14.         if (length == 1) return *first1 == *first2;
  16.         // 剪枝，提前返回
  17.         int A[26]; // 每个字符的计数器
  18.         fill(A, A + 26, 0);
  19.         for(int i = 0; i < length; i++) A[*(first1+i)-'a']++;
  20.         for(int i = 0; i < length; i++) A[*(first2+i)-'a']--;
  21.         for(int i = 0; i < 26; i++) if (A[i] != 0) return false;
  23.         for (int i = 1; i < length; ++i)
  24.             if ((isScramble(first1, first1 + i, first2)
  25.                  && isScramble(first1 + i, last1, first2 + i))
  26.                     || (isScramble(first1, first1 + i, last2 - i)
  27.                             && isScramble(first1 + i, last1, first2)))
  28.                 return true;
  30.         return false;
  31.     }
  32. };

备忘录法

  1. typedef string::const_iterator Iterator;
  2. typedef tuple Key;
  3. // 定制一个哈希函数
  4. namespace std {
  5. template<> struct hash {
  6.     size_t operator()(const Key & x) const {
  7.         Iterator first1, last1, first2;
  8.         tie(first1, last1, first2) = x;
  10.         int result = *first1;
  11.         result = result * 31 + *last1;
  12.         result = result * 31 + *first2;
  13.         result = result * 31 + *(next(first2, distance(first1, last1)-1));
  14.         return result;
  15.     }
  16. };
  17. }
  19. // Scramble String
  20. // 递归+unordered_map做cache，比map快
  21. // 时间复杂度O(n^3)，空间复杂度O(n^3)
  22. class Solution {
  23. public:
  24.     unordered_map cache;
  26.     bool isScramble(const string& s1, const string& s2) {
  27.         cache.clear();
  28.         return isScramble(s1.begin(), s1.end(), s2.begin());
  29.     }
  31.     bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
  32.         auto length = distance(first1, last1);
  33.         auto last2 = next(first2, length);
  35.         if (length == 1)
  36.             return *first1 == *first2;
  38.         for (int i = 1; i < length; ++i)
  39.             if ((getOrUpdate(first1, first1 + i, first2)
  40.                     && getOrUpdate(first1 + i, last1, first2 + i))
  41.                     || (getOrUpdate(first1, first1 + i, last2 - i)
  42.                             && getOrUpdate(first1 + i, last1, first2)))
  43.                 return true;
  45.         return false;
  46.     }
  48.     bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
  49.         auto key = make_tuple(first1, last1, first2);
  50.         auto pos = cache.find(key);
  52.         return (pos != cache.end()) ?
  53.                 pos->second : (cache[key] = isScramble(first1, last1, first2));
  54.     }
  55. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dp/scramble-string.html