Scramble String, Leetcode 解题笔记

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.

这题难度很高,面试中遇到这种题估计是做不出来的,除非之前见过。网上流行两种解法,第一种是递归,比较容易理解,关键点是找到规律。对付复杂问题的方法是从简单的特例来思考,从而找出规律。
先考察简单情况:
字符串长度为1:很明显,两个字符串必须完全相同才可以。
字符串长度为2:当s1=”ab”, s2只有”ab”或者”ba”才可以。
对于任意长度的字符串,我们可以把字符串s1分为a1,b1两个部分,s2分为a2,b2两个部分,满足((a1~a2) && (b1~b2))或者 ((a1~b2) && (a1~b2))

public class Solution {
    public boolean isScramble(String s1, String s2) {
        
        int m = s1.length();
        int n = s2.length();
        if(m != n) return false;
        if(s1.equals(s2)) return true;
        char[] one = s1.toCharArray();
        char[] two = s2.toCharArray();
        Arrays.sort(one);
        Arrays.sort(two);
        for(int i = 0; i < m; i++){
            if(one[i] != two[i])
                return false;
        }
        
        for(int i = 1; i < s1.length(); i++){
            String sub11 = s1.substring(0, i);
            String sub12 = s1.substring(i, m);
            String sub21 = s2.substring(0, i);
            String sub22 = s2.substring(i, m);
            
            if(isScramble(sub11, sub21) && isScramble(sub12, sub22))
                return true;
            
            sub21 = s2.substring(0, m-i);
            sub22 = s2.substring(m-i, m);
            if(isScramble(sub11, sub22) && isScramble(sub12, sub21))
                return true;
        }
        return false;
    }
}

还有一种更快的方法,是利用动态规划,思路很绕,这里不写了,感兴趣的可以自己去搜一下。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s