87. Scramble String (Java)

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.

Example 1:

Input: s1 = "great", s2 = "rgeat"

Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"

Output: false

思路：对付复杂问题的方法是从简单的特例来思考。简单情况：

如果字符串长度为1，那么必须两个字符串完全相同；
如果字符串长度为2，例如s1='ab'，则s2='ab'或s2='ba'才行
如果字符串任意长度，那么可以把s1分为a1, b1两部分，s2分为a2,b2两部分。需要满足：((a1=a2)&&(b1=b2)) || ((a1=b2)&&(a2=b1)) =>可用递归

class Solution {

    public boolean isScramble(String s1, String s2) {

        if(s1.length()==1) return s1.equals(s2);

        String s11;

        String s12;

        String s21;

        String s22;

        for(int i = 1; i <= s1.length(); i++){

            s11 = s1.substring(0, i);

            s12 = s1.substring(i);

            s21 = s2.substring(0,i);

            s22 = s2.substring(i);

            if(isScramble(s11,s21) && isScramble(s12,s22)) return true;

            if(isScramble(s11,s22) && isScramble(s12,s21)) return true;

        }

        return false;

    }

}

Result: Time Limit Exceeded

解决方法：动态规划。三维状态dp[i][j][k]，前两维分别表示s1和s2的下标起始位置，k表示子串的长度。dp[i][j][k]=true表示s1(i, i+k-1)和s2(j, j+k-1)是scramble。

结合递归法中的逻辑，dp[i][j][k]=true的条件是s1(i, i+split-1)=s2(j, j+split-1) && s1(i+split, i+k-1) = s2(j+split, j+k-1) 或者 s1(i, i+split-1)=s2(j+k-split, j+k-1) && s1(i+split, i+k-1) = s2(j, j+k-split-1)

所以状态转移方程是：如果dp[i][j][split] = true && dp[i+split][j+split][k-split] = true 或者 dp[i][j+k-split][split]=true && dp[i+split][j][k-split]=true，那么dp[i][j][k]=true

初始状态：当k=1的时候dp[i][j][1]=true的条件是s1(i)=s2(j)

class Solution {

    public boolean isScramble(String s1, String s2) {

        if(s1.length()== 0 || s1.equals(s2)) return true;

        boolean dp[][][] = new boolean[s1.length()][s1.length()][s1.length()+1];

        //initial state

        for(int i = 0; i < s1.length(); i++){

            for(int j = 0; j < s2.length(); j++){

                dp[i][j][1] = s1.charAt(i)==s2.charAt(j);

            }

        }

        //state transfer

        for(int k = 2; k <= s1.length(); k++){

            for(int i = 0; i+k-1 < s1.length(); i++){

                for(int j = 0; j+k-1 < s1.length(); j++){

                    for(int split = 1; split < k; split++){

                        //如果dp[i][j][split] = true && dp[i+split][j+split][k-split] = true 或者 dp[i][j+k-split][split]=true && dp[i+split][j][k-split]=true，那么dp[i][j][k]=true

                        if((dp[i][j][split] && dp[i+split][j+split][k-split]) || (dp[i][j+k-split][split] && dp[i+split][j][k-split])){

                            dp[i][j][k] = true;

                            break;

                        }

                    }

                }

            }

        }

        return dp[0][0][s1.length()];

    }

}

巴特西

87. Scramble String (Java)

最新文章

热门文章