[LintCode/LeetCode] Scramble String

MASAILA 發布于2019-08-14 15:45 / 3544人閱讀

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

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

首先將兩個字符串化成字符數組，排序后逐位比較，確定它們等長且具有相同數量的相同字符。
然后，從第一個字符開始向后遍歷，判斷s1和s2中以這個坐標為中點的左右兩個子字符串是否滿足第一步中互為scramble string的條件：
設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;
    }
}

GPU云服務器云服務器 Scramble String _String public string

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65997.html

leetcode87. Scramble String

摘要：允許對非葉結點的兩個子節點進行旋轉，且允許對多個非葉節點進行子節點的旋轉操作。將該操作生成的新字符串成為。現在輸入兩個字符串，判斷該兩個字符串是否是。不僅要考慮數組的劃分，還要考慮所有可能的旋轉。題目要求 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empt...

BlackFlagBin 2019-08-15 11:13 評論0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評論0 收藏0
[LintCode/LeetCode] Two Strings are Anagrams/Valid

摘要：建立一個長度為的數組，統計所有個字符在出現的次數，然后減去這些字符在中出現的次數。否則，循環結束，說明所有字符在和中出現的次數一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

vslam 2019-08-14 15:22 評論0 收藏0
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 評論0 收藏0
[LintCode/LeetCode] Largest Number [Comparator的使用]

摘要：先將轉化為，否則無法使用，其實轉為也可以，這里用為例。然后就是最關鍵的一步創造一個，用以從大到小排列所有的元素。注意這里的順序不能變。再將排列好的元素放入一個里，然后將轉化為。 Problem Given a list of non negative integers, arrange them such that they form the largest number. Examp...

xietao3 2019-08-14 15:21 評論0 收藏0