[LintCode/LeetCode] Scramble String
文章目录
Problem
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.
Challenge
O(n3) time
Note
首先将两个字符串化成字符数组,排序后逐位比较,确定它们等长且具有相同数量的相同字符。
然后,从第一个字符开始向后遍历,判断s1和s2中以这个坐标为中点的左右两个子字符串是否满足第一步中互为scramble string的条件:
设s1分为a1和b1,s2分为a2和b2。若a1和a2满足且b1和b2满足(令a1和a2长度相等,b1和b2长度相等),或a1和b2满足且a2和b1满足(令a1和b2长度相等,a2和b1长度相等),就break出来,返回true;
若遍历完s1,仍旧没有满足条件的情况,返回false。
Solution
public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
char[] sc1 = s1.toCharArray();
char[] sc2 = s2.toCharArray();
Arrays.sort(sc1);
Arrays.sort(sc2);
for (int i = 0; i < sc1.length; i++) {
if (sc1[i] != sc2[i]) return false;
}
int mid = 1;
boolean res = false;
while (mid < s1.length()) {
res = (isScramble(s1.substring(0, mid), s2.substring(0, mid)) &&
isScramble(s1.substring(mid, s1.length()), s2.substring(mid, s2.length())))
|| (isScramble(s1.substring(0, mid), s2.substring(s2.length()-mid, s2.length())) &&
isScramble(s1.substring(mid, s1.length()), s2.substring(0, s2.length()-mid)));
if (res) break;
mid++;
}
return res;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论