搅乱字符串

[编程题]搅乱字符串

热度指数：10276 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

题目给出一个字符串s1，我们可以用递归的方法将字符串分成两个非空的子串来将s1表示成一个二叉树

下面是s1=“coder”的一种二叉树的表现形式：

coder

/ \

co der

/ \ / \

c o d er

/ \

e r

将字符串乱序的方法是：选择任意的非叶子节点，交换它的两个孩子节点。

例如：如果我们选择节点“co”交换他的两个孩子节点，就会产生一个乱序字符串"ocder".

ocder

/ \

oc der

/ \ / \

o c d er

/ \

e r

我们称"ocder"是"coder"的一个乱序字符串。

类似的：如果我们继续交换“der”的两个孩子节点和“at”的两个孩子节点，会产生乱序字符串"ocred"

    ocred
   /    \
  oc    red
 / \    /  \
o   c  re   d
       / \
      r   e

我们称"ocred"是"coder"的一个乱序字符串。

给出两个长度相同的字符串s1 和 s2，请判断s2是否是s1的乱序字符串。

示例1

输入

"ab","ab"

输出

true

示例2

输入

"ba","ab"

输出

true

算法知识视频讲解

Java

Fubuki_0v0

public boolean isScramble (String s1, String s2) {
// write code here
if(s1==null || s2==null) {
return false;
}
if(s1.length()!=s2.length()) {
return false;
}
if(s1.length()==1) {
return s1.equals(s2);
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
for(int i=0; i<c1.length; i++) {
if(c1[i]!=c2[i]) {
return false;
}
}

for(int i=1; i<s1.length(); i++) {
String s1l = s1.substring(0, i);
String s1r = s1.substring(i);
String s2l = s2.substring(0, i);
String s2r = s2.substring(i);

if(isScramble(s1l, s2l) && isScramble(s1r, s2r)) {
return true;
}

int j = s2.length()-i;
s2l = s2.substring(0, j);
s2r = s2.substring(j);

if(isScramble(s1l, s2r) && isScramble(s1r, s2l)) {
return true;
}
}
return false;
}

发表于 2020-07-15 11:33:47 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
    public boolean isScramble(String s1, String s2) {
		if(s1.length() != s2.length()) return false;
		if(s1.length() == 1 || s2.length() == 1) return s1.equals(s2);
		char[] arr1 = s1.toCharArray();
		char[] arr2 = s2.toCharArray();
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		for (int i = 0; i < arr1.length; i ++) {
			if(arr1[i] != arr2[i]) return false;
		}
		for (int i = 1; i < s1.length(); i ++) {
			String s1left = s1.substring(0, i);
			String s1rigt = s1.substring(i);
			String s2left = s2.substring(0, i);
			String s2right = s2.substring(i);
			if(isScramble(s1left, s2left) && isScramble(s1rigt, s2right)) return true;
			s2left = s2.substring(0, s2.length() - i);
			s2right = s2.substring(s2.length() - i);
			if(isScramble(s1left, s2right) && isScramble(s1rigt, s2left)) return true;
		}
		return false;
	}
}

发表于 2017-03-26 13:31:54 回复(0)

Java

城市里的养猫者

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;  int[] letters = new int[26]; for (int i=0; i<s1.length(); i++) { letters[s1.charAt(i)-'a']++; letters[s2.charAt(i)-'a']--; }
        for (int i=0; i<26; i++) if (letters[i]!=0) return false; for (int i=1; i<s1.length(); i++) { if (isScramble(s1.substring(0,i), s2.substring(0,i))  && isScramble(s1.substring(i), s2.substring(i))) return true; if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i))  && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true; }
        return false; }
}