[LintCode/LeetCode] Scramble String

MASAILA 發(fā)布于2019-08-14 15:45 / 3550人閱讀

摘要：首先將兩個字符串化成字符數(shù)組，排序后逐位比較，確定它們等長且具有相同數(shù)量的相同字符。然后，從第一個字符開始向后遍歷，判斷和中以這個坐標(biāo)為中點的左右兩個子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。

Problem

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.

Challenge

O(n3) time

Note

首先將兩個字符串化成字符數(shù)組，排序后逐位比較，確定它們等長且具有相同數(shù)量的相同字符。
然后，從第一個字符開始向后遍歷，判斷s1和s2中以這個坐標(biāo)為中點的左右兩個子字符串是否滿足第一步中互為scramble string的條件：
設(shè)s1分為a1和b1，s2分為a2和b2。若a1和a2滿足且b1和b2滿足（令a1和a2長度相等，b1和b2長度相等），或a1和b2滿足且a2和b1滿足（令a1和b2長度相等，a2和b1長度相等），就break出來，返回true；
若遍歷完s1，仍舊沒有滿足條件的情況，返回false。

Solution

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        char[] sc1 = s1.toCharArray();
        char[] sc2 = s2.toCharArray();
        Arrays.sort(sc1);
        Arrays.sort(sc2);
        for (int i = 0; i < sc1.length; i++) {
            if (sc1[i] != sc2[i]) return false;
        }
        int mid = 1;
        boolean res = false;
        while (mid < s1.length()) {
            res = (isScramble(s1.substring(0, mid), s2.substring(0, mid)) && 
                    isScramble(s1.substring(mid, s1.length()), s2.substring(mid, s2.length())))
                    ||  (isScramble(s1.substring(0, mid), s2.substring(s2.length()-mid, s2.length())) && 
                    isScramble(s1.substring(mid, s1.length()), s2.substring(0, s2.length()-mid)));
            if (res) break;
            mid++;
        }
        return res;
    }
}