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. public class Solution {
  5.     public boolean isScramble(String s1, String s2) {
  6.         return isScramble(s1, 0, s1.length(), s2, 0);
  7.     }
  8.     private static boolean isScramble(String s1, int begin1, int end1,
  9.                                       String s2, int begin2) {
  10.         final int length = end1 - begin1;
  11.         final int end2 = begin2 + length;
  13.         if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);
  15.         for (int i = 1; i < length; ++i)
  16.             if ((isScramble(s1, begin1, begin1 + i, s2, begin2)
  17.                     && isScramble(s1, begin1 + i, end1, s2, begin2 + i))
  18.                     || (isScramble(s1, begin1, begin1 + i, s2, end2 - i)
  19.                     && isScramble(s1, begin1 + i, end1, s2, begin2)))
  20.                 return true;
  22.         return false;
  23.     }
  24. }

动规

  1. // Scramble String
  2. // 动规，时间复杂度O(n^3)，空间复杂度O(n^3)
  3. public class Solution {
  4.     public boolean isScramble(String s1, String s2) {
  5.         final int N = s1.length();
  6.         if (N != s2.length()) return false;
  8.         // f[n][i][j]，表示长度为n，起点为s1[i]和
  9.         // 起点为s2[j]两个字符串是否互为scramble
  10.         boolean[][][] f = new boolean[N+1][N][N];
  12.         for (int i = 0; i < N; i++)
  13.             for (int j = 0; j < N; j++)
  14.                 f[1][i][j] = s1.charAt(i) == s2.charAt(j);
  16.         for (int n = 1; n

递归+剪枝

  1. // Scramble String
  2. // 递归+剪枝
  3. // 时间复杂度O(n^6)，空间复杂度O(1)
  4. public class Solution {
  5.     public boolean isScramble(String s1, String s2) {
  6.         return isScramble(s1, 0, s1.length(), s2, 0);
  7.     }
  8.     private static boolean isScramble(String s1, int begin1, int end1,
  9.                                       String s2, int begin2) {
  10.         final int length = end1 - begin1;
  11.         final int end2 = begin2 + length;
  12.         if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);
  14.         // 剪枝，提前返回
  15.         int[] A = new int[26]; // 每个字符的计数器
  16.         for(int i = 0; i < length; i++) A[s1.charAt(begin1+i)-'a']++;
  17.         for(int i = 0; i < length; i++) A[s2.charAt(begin2+i)-'a']--;
  18.         for(int i = 0; i < 26; i++) if (A[i] != 0) return false;
  20.         for (int i = 1; i < length; ++i)
  21.             if ((isScramble(s1, begin1, begin1 + i, s2, begin2)
  22.                     && isScramble(s1, begin1 + i, end1, s2, begin2 + i))
  23.                     || (isScramble(s1, begin1, begin1 + i, s2, end2 - i)
  24.                     && isScramble(s1, begin1 + i, end1, s2, begin2)))
  25.                 return true;
  27.         return false;
  28.     }
  29. }

备忘录法

  1. // Scramble String
  2. // 递归+map做cache
  3. // 时间复杂度O(n^3)，空间复杂度O(n^3), TLE
  4. public class Solution {
  5.     public boolean isScramble(String s1, String s2) {
  6.         cache.clear();
  7.         return isScramble(s1, 0, s1.length(), s2, 0);
  8.     }
  10.     final private HashMap cache = new HashMap<>();
  12.     private boolean isScramble(String s1, int begin1, int end1,
  13.                                String s2, int begin2) {
  14.         final int length = end1 - begin1;
  15.         final int end2 = begin2 + length;
  17.         if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);
  19.         for (int i = 1; i < length; ++i)
  20.             if ((getOrUpdate(s1, begin1, begin1 + i, s2, begin2)
  21.                     && getOrUpdate(s1, begin1 + i, end1, s2, begin2 + i))
  22.                     || (getOrUpdate(s1, begin1, begin1 + i, s2, end2 - i)
  23.                     && getOrUpdate(s1, begin1 + i, end1, s2, begin2)))
  24.                 return true;
  26.         return false;
  27.     }
  29.     boolean getOrUpdate(String s1, int begin1, int end1,
  30.                      String s2, int begin2) {
  31.         Triple key = new Triple(begin1, end1, begin2);
  32.         if (!cache.containsKey(key)) {
  33.             boolean result = isScramble(s1, begin1, end1, s2, begin2);
  34.             cache.put(key, result);
  35.             return result;
  36.         } else {
  37.             return cache.get(key);
  38.         }
  39.     }
  40.     static class Triple {
  41.         private int i;
  42.         private int j;
  43.         private int k;
  45.         public Triple(int i, int j, int k) {
  46.             this.i = i;
  47.             this.j = j;
  48.             this.k = k;
  49.         }
  50.         @Override
  51.         public int hashCode() {
  52.             int hash = 0;
  53.             hash = i * 31 + j;
  54.             hash = hash * 31 * k;
  55.             return hash;
  56.         }
  57.         @Override
  58.         public boolean equals(Object other) {
  59.             if (this == other) return true;
  60.             if (this.hashCode() != other.hashCode()) return false;
  61.             if (!(other instanceof Triple)) return false;
  62.             Triple o = (Triple)other;
  63.             return this.i == o.i && this.j == o.j && this.k == o.k;
  64.         }
  65.     }
  66. }

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