题目描述

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.

java实现

import java.util.Arrays;public class Solution1 {public boolean isScramble(String s1, String s2) {if (s1.length() != s2.length())return false;if (s1.length() == 0 || s1.equals(s2)) {return true;}if (!isValid(s1, s2)) {return false;}for (int i = 1; i < s1.length(); i++) {String s11 = s1.substring(0, i);String s12 = s1.substring(i, s1.length());String s21 = s2.substring(0, i);String s22 = s2.substring(i, s2.length());String s23 = s2.substring(s2.length() - i, s2.length());String s24 = s2.substring(0, s2.length() - i);if (isScramble(s11, s21) && isScramble(s12, s22))return true;if (isScramble(s11, s23) && isScramble(s12, s24))//有可能交换，做交叉验证return true;}return false;}private boolean isValid(String s1, String s2) {char[] arr1 = s1.toCharArray();char[] arr2 = s2.toCharArray();Arrays.sort(arr1);Arrays.sort(arr2);if (!(new String(arr1)).equals(new String(arr2))) {return false;}return true;}public static void main(String[] args) {String s1 = "great";String s2 = "rwgat";if(new Solution1().isScramble(s1, s2)){System.out.println("yes");}}}

参考：这里写链接内容

总结

以上是生活随笔为你收集整理的Scramble String的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。