Java for LeetCode 087 Scramble String

浏览数：54 / 时间：2015年06月08日

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":

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".

解题思路：

这道题用的是递归遍历的方法，JAVA实现如下：

static public boolean isScramble(String s1, String s2) {
		if (!isMatch(s1, s2))
			return false;
		if (s1.length() == 0)
			return true;
		else if (s1.length() == 1) {
			if (s1.charAt(0) == s2.charAt(0))
				return true;
			return false;
		} else if (s1.length() == 2) {
			if (s1.charAt(0) == s2.charAt(0) && s1.charAt(1) == s2.charAt(1))
				return true;
			else if (s1.charAt(1) == s2.charAt(0)
					&& s1.charAt(0) == s2.charAt(1))
				return true;
			return false;
		}
		for (int i = 0; i < s1.length() - 1; i++) {
			if (isScramble(s1.substring(0, i + 1), s2.substring(0, i + 1))
					&& isScramble(s1.substring(i + 1, s1.length()),
							s2.substring(i + 1, s1.length())))
				return true;
                if (isScramble(s1.substring(0, i + 1),
					s2.substring(s1.length()-i-1, s1.length()))
					&& isScramble(s1.substring(i+1, s1.length()),
							s2.substring(0, s1.length()-i-1)))
				return true;
		}
		return false;
	}

	static public boolean isMatch(String s1, String s2) {
		if (s1.length() != s2.length())
			return false;
		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;
		return true;
	}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 087 Scramble String