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.
这道题是给定一个字符串,然后用二叉树的形式保存下来,然后可以交换兄弟节点,要求判断第二个字符串是否可以由这种方式得到。
1、如果从二叉树的存储方式入手,想要找到存储二叉树的结果,很困难,所以要从结果入手。
2、刚开始的想法是,遍历后一个字符串,然后看每一个字母的相邻字母是否在前一个字符串中是否相邻
a、如果都不相邻,那么返回false。
b、如果相邻,那么将这两个字母看成一个字符,接着判断。
c、但是最后循环出了问题,最后没有得到结果。
3、顺着题意想,直接递归就能得到结果。
public class Solution { public boolean isScramble(String s1, String s2) { char[] v1 = s1.toCharArray(); char[] v2 = s2.toCharArray(); return isScramble(v1, 0, v1.length - 1, v2, 0, v2.length - 1); } private boolean isScramble(char[] v1, int start1, int end1, char[] v2, int start2, int end2) { int[] letters = new int[26]; boolean isSame = true; for (int i = start1, j = start2; i <= end1; i++, j++) { letters[v1[i] -'a']++; letters[v2[j] -'a']--; isSame = isSame && v1[i] == v2[j]; } if (isSame) return true; for (int i = 0; i < 26; i++) if (letters[i] != 0) return false; for (int i = start1, j = start2; i < end1; i++, j++) { if (isScramble(v1, start1, i, v2, start2, j) && isScramble(v1, i + 1, end1, v2, j + 1, end2)) return true; if (isScramble(v1, start1, i, v2, end2 - j + start2, end2) && isScramble(v1, i + 1, end1, v2, start2, end2 - j + start2 - 1)) return true; } return false;} }
这样就基本达到最快,还有就是网上有很多dp的算法,但这里并不是很适合,速度反倒没有递归快,复杂度达到了三次方。这里就不再贴上答案。