leetcode87.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":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          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".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          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".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      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.

将一个字符串逐渐分解为一个叶节点为单个字母的树。允许对非叶结点的两个子节点进行旋转，且允许对多个非叶节点进行子节点的旋转操作。将该操作生成的新字符串成为scrambled string。现在输入两个字符串，判断该两个字符串是否是scrambled string。

思路和代码

在一开始，我的思路出现了局限性，我希望通过列出所有的s1可以生成的scrambled string来判断s2是否在该集合中。但是后序就会发现，如果要计算s1全部的scrambled string显然是非常不明智的。不仅要考虑数组的划分，还要考虑所有可能的旋转。
之后，我就想到了利用递归来判断二者究竟是不是互相旋转生成的。我们先从一次旋转来看，比如great和reatg，然后再进行一次旋转变成eratg。我们可以看到，reat和erat也是scrambled string。也就是说，我们只要找到合适的旋转点，并判断s1和s2在旋转点左右的子字符串是否互为scrambled string就行。

递归的代码非常简洁清晰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isScramble(String s1, String s2) {
    if(s1.equals(s2)) return true;
    int[] alpha = new int[26];
    for(int i = 0 ; i<s1.length() ; i++){
        alpha[s1.charAt(i)-'a']++;
        alpha[s2.charAt(i)-'a']--;
    }
    for(int i = 0 ; i<26 ; i++){
        if(alpha[i]!=0) return false;
    }
    for(int i = 0 ; i<s1.length() ; i++){
        if(isScramble(s1.substring(0,i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) return true;
        if(isScramble(s1.substring(0,i), s2.substring(s2.length()-i)) && isScramble(s1.substring(s1.length()-i), s2.substring(0,i))) return true;
    }
    return false;
}