思路:
1 递归:
简单的说,就是s1和s2是scramble的话,那么必然存在一个在s1上的长度l1,将s1分成s11和s12两段,同样有s21和s22。
那么要么s11和s21是scramble的并且s12和s22是scramble的;
要么s11和s22是scramble的并且s12和s21是scramble的。
如果要能通过OJ,还必须把字符串排序后进行剪枝
http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Ascramble-string%EF%BC%8C%E4%B8%89%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
2 DP:
使用了一个三维数组boolean result[len][len][len],其中第一维为子串的长度,第二维为s1的起始索引,第三维为s2的起始索引。
result[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]变化得来。
http://www.blogjava.net/sandy/archive/2013/05/22/399605.html
package Level5;
import java.util.Arrays;
/**
* 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":
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.
*
*/
public class S87 {
public static void main(String[] args) {
String s1 = "abab";
String s2 = "bbaa";
System.out.println(isScramble(s1, s2));
System.out.println(isScrambleDP(s1, s2));
}
public static boolean isScramble(String s1, String s2) {
if(s1.length() != s2.length()){
return false;
}
if(s1.length()==1 && s2.length()==1){
return s1.charAt(0) == s2.charAt(0);
}
// 排序后可以通过
char[] s1ch = s1.toCharArray();
char[] s2ch = s2.toCharArray();
Arrays.sort(s1ch);
Arrays.sort(s2ch);
if(!new String(s1ch).equals(new String(s2ch))){
return false;
}
for(int i=1; i<s1.length(); i++){ // 至少分出一个字符出来
String s11 = s1.substring(0, i);
String s12 = s1.substring(i);
String s21 = s2.substring(0, i);
String s22 = s2.substring(i);
// System.out.println(s1 + "-" + s2 + ": "+ s11 + ", " + s12 + ", " + s21 + ", " + s22);
// 检测前半部是否匹配
if(isScramble(s11, s21) && isScramble(s12, s22)){
return true;
}
// 前半部不匹配,检测后半部是否匹配
s21 = s2.substring(0, s2.length()-i);
s22 = s2.substring(s2.length()-i);
if(isScramble(s11, s22) && isScramble(s12, s21)){
return true;
}
}
return false;
}
public static boolean isScrambleDP(String s1, String s2) {
int len = s1.length();
if(len != s2.length()){
return false;
}
if(len == 0){
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
// canTransform 第一维为子串的长度delta,第二维为s1的起始索引,第三维为s2的起始索引
// canTransform[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]变化得来。
boolean[][][] canT = new boolean[len][len][len];
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){ // 如果字符串总长度为1,则取决于唯一的字符是否想到
canT[0][i][j] = c1[i] == c2[j];
}
}
for(int k=2; k<=len; k++){ // 子串的长度
for(int i=len-k; i>=0; i--){ // s1[i...i+k]
for(int j=len-k; j>=0; j--){ // s2[j...j+k]
boolean canTransform = false;
for(int m=1; m<k; m++){ // 尝试以m为长度分割子串
// canT[k][i][j]
canTransform = (canT[m-1][i][j] && canT[k-m-1][i+m][j+m]) || // 前前后后匹配
(canT[m-1][i][j+k-m] && canT[k-m-1][i+m][j]); // 前后后前匹配
if(canTransform){
break;
}
}
canT[k-1][i][j] = canTransform;
}
}
}
return canT[len-1][0][0];
}
}
分享到:
相关推荐
ScrambleJS JavaScript中数组和字符串的有效改组在做了ScrambleJS可作为Node模块使用$ npm install scramble --save 以及凉亭组件$ bower install scramble --save 或者可以直接在此仓库中设置$ git clone git@...
PRBS & SCRAMBLE的实现 原理讲解
这是游戏Xross Scramble非常难找的免dvd补丁,基本上只有游戏本体依然无法运行游戏,只有打上免DVD补丁才能顺利运行。
cramble 是用于加扰文本串的库。 Scr\m6ble 是一个用于 scrvmling 流文本的 l1brary。 纺织的Ssramble 是 ╗ 一个 lbMary,用于拼写 tlibrary sleams ScrambFe 是一个用于 cra=bling tex¯ 的库。 Scramble 是 al$b...
争夺 客观的 使用Vue Framework,创建游戏Scramble的交互式版本。 有关完整的说明,请参阅“。
高中英语单词天天记scramble素材
“扰乱您的社交网络数据!” -使用Scramble,您可以有选择地强制您对社交网络(如Facebook或Twitter)上的内容执行访问控制首选项...
Xchat的New Scramble游戏。 Xchat的一个简单项目。
同时应注意,加密算法应当引用/src/Model下Scramble的接口,并封装在包src.Model下。然后需要实现Scamble接口里的函数public BufferedImage scrambling(File srcImageFile, int period);。其中,scrImageFile为输入...
Blender-Scramble-Addon-源码.rar
2种关于DVD CSS(Content Scramble System) 加密算法实现及验证。
cat map function to scramble a one dimentson sequence
前端开源库-email-scramble电子邮件混乱,电子邮件地址和电话号码混乱与rot-18,以隐藏他们的僵尸。
语言:English (United States) 只需单击一个按钮,即可使每个网页变得有趣。 在Elingsh工会会上,一位主持人致辞,说这不是在一个杂乱无章的地方,在olny iprmoetnt tihng是在第一个,而lsat ltteer在在rghit上。...
简单的随机单词打乱-检查输入是否与随机单词匹配。特征document.querySelector()。 const myArray = [“ javascript”,“网站”,“ html”,“文档”,“课程”,“新”]; button.addEventListener(“ click...
原始文件scramble.io仍然存在。 我仍然每天都在使用它。 不过可能会更好。 这是我所学到的: 人们想保留他们现有的电子邮件地址。 许多人已经有几个,并且不希望另一个以@scramble.io结尾为了获得端到端加密电子...
从: 至: 为了使用它:使用Processing打开pixel_scramble.pde并运行它选择您要加扰的图像左键单击以生成一个新图像,该图像将所选像素的像素置乱按ENTER键将新图像另存为.png 重复步骤4和5.以生成并保存尽可能多的...
字符串 Valid Palindrome Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix Valid Number Integer to...
争夺一个拼字游戏。 尝试在时限内尽可能多地解读单词。 该项目是使用Angular和Node构建的。 用于随机单词的Wordnik API。开始克隆此仓库并运行npm install 。 使用npm start启动服务器,然后在浏览器中转到localhost...