leetcode题解 problem87 Scramble String

Tags:

题解:

设s1,s2是两个长度都为len的字符串(把s1、s2当做字符数组理解)

设状态量res[n][i][j],(n < len, i <= n, j <= n), 元素是bool值

res的含义:

长度为n,以i位置为起点的子串s1[i, i + n], 以j位置为起点的子串s2[i, i + n], res[n][i][j]标志了这2个子串是不是Scramble

那么很显然,res[len-1][0][0]就是我们要的解。

状态转移方程:

res[n][i][j] = ( res[k][i][j] && res[n - k][i + k][j + k] ) || ( res[k][i][j + n - k] && res[n - k][i + k][j] ) ** (1<=k<n) **

这个式子看起来很吓人。先做个分解:

设 A = res[k][i][j] && res[n - k][i + k][j + k] = A1 && A2

设 B = res[k][i][j + n - k] && res[n - k][i + k][j] = B1 && B2

设 C = res[n][i][j] = A || B

也就是说,只要A、B中有一个为T,那么C就为T; 而A、B为T的条件分别是,A1和A2同时为真、B1和B2同时为真。

A1、A2、B1、B2的含义是什么呢?举例说明一下:

 1 great
 2 rgtae
 3 
 4 n = 5, k = 1, i = 0, j = 0 时:
 5 res[k][i][j]           &&     res[n - k][i + k][j + k]
 6    g|****                          *|reat
 7    r|****                          *|gtae
 8    A1 = F                          A2 = F
 9 
10 res[k][i][j + n - k]   &&      res[n - k][i + k][j]
11    g|****                          *|reat
12    ****|e                          rgta|*
13    B1 = F                          B2 = F
14 
15 显然 C = A || B = (F && F) || (F && F) = F
16 
17 n = 5, k = 2, i = 0, j = 0 时:
18 res[k][i][j]           &&     res[n - k][i + k][j + k]
19    gr|***                          **|eat
20    rg|***                          **|tae
21    A1 = T                          A2 = T
22 
23 res[k][i][j + n - k]   &&      res[n - k][i + k][j]
24    gr|***                          **|eat
25    ***|ae                          rgt|**
26    B1 = F                          B2 = F
27 
28 显然 C = A || B = (T && T) || (F && F) = T
  1. 当(A1 && A2) = T时, s1-left和s2-left互为Scramble, s1-right和s2-right互为Scramble;

  2. 当(B1 && B2) = T时, s1-left和s2-right互为Scramble, s1-right和s2-left互为Scramble。

状态转移方程有了,还差个初始化状态:

n = 0时,s1、s2退化成s1[i]和s2[j],那么res[0][i][j] 等于 s1[i] == s2[j]

代码如下:

 1   bool isScramble(string s1, string s2) {
 2      int len = s1.length();
 3      if (len != s2.length()){
 4          return false;
 5      }
 6      if (len == 0){
 7          return true;
 8      }
 9      vector<vector<vector<bool>>> result(len);
10      for (int i = 0; i<len; ++i){
11          result[i].resize(len);
12          for (int j = 0; j<len; ++j){
13              result[i][j].resize(len);
14              for (int k = 0; k<len; ++k)
15                  result[i][j][k] = false;
16              result[0][i][j] = (s1[i] == s2[j]);//tricky
17          }
18      }
19 
20      for (int n = 2; n <= len; ++n){
21          for (int i = len - n; i >= 0; --i){
22              for (int j = len - n; j >= 0; --j){
23                  bool r = false;
24                  for (int k = 1; k < n && !r; ++k){
25                      r = (result[k - 1][i][j] && result[n - k - 1][i + k][j + k]) 
26                          || (result[k - 1][i][j + n - k] && result[n - k - 1][i + k][j]);
27                  }
28                  result[n - 1][i][j] = r;
29              }
30          }
31      }
32      return result[len - 1][0][0];
33  }

rumtime 196ms...别人最快有4ms的。应该是4重循环的自底而上的DP计算导致这么慢的,必须全部状态都算出来才可以返回最终结果。

(未经授权禁止转载)
Written on July 24, 2015

博主将十分感谢对本文章的任意金额的打赏^_^