87. Scramble String

网友投稿 754 2022-10-09

87. Scramble String

87. Scramble String

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

\ gr eat / \ / \g r e at / \

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

\ rg eat / \ / \r g e at / \

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

\ rg tae / \ / \r g ta e / \

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、遍历后一个字符串,然后看每一个字母的相邻字母是否在前一个字符串中是否相邻 a、如果都不相邻,那么返回false。 b、如果相邻,那么将这两个字母看成一个字符,接着判断。 c、但是最后循环出了问题,最后没有得到结果。 2、递归就能得到结果。

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

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:mpvue 自定义小程序tabBar(mpvue停止维护了)
下一篇:115. Distinct Subsequences
相关文章

 发表评论

暂时没有评论,来抢沙发吧~