[LintCode/LeetCode] Scramble String

MASAILA 发布于2019-08-14 15:45 / 3543人阅读

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。

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;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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