s******n
发帖数: 3946 | 1 递归非DP做法
bool isScramble(char* str1, char* str2, int length) {
if (length==1) return *str1 == *str2;
for (int i=1; i
if (isScramble(str1, str2+(length-i), i)
&& isScramble(str1+i, str2, length-i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1+i, str2+i, length-i))
return true;
}
return false;
}
递归DP做法
class Solution {
char* str1;
char* str2;
int m;
int m2;
int m3;
int* DP;
#define dp(i,j,k) DP[m2 * (i) + m * (j) + (k) ]
public:
Solution(cha... 阅读全帖 |
|
j*****y
发帖数: 1071 | 2 多谢二爷，这是我的 recursive
class Solution {
public:
bool isScramble(const string &s1, int start1, int end1, const string &s2
, int start2, int end2)
{
string s = s1.substr(start1, end1 - start1 + 1);
string t = s2.substr(start2, end2 - start2 + 1);
sort(s.begin(), s.end());
sort(t.begin(), t.end());
if(s != t)
{
return false;
}
if(s1.substr(start1, end1 - start1 + 1) == s2.substr(start2, end2 -
start2 + 1))
{
... 阅读全帖 |
|
a***e
发帖数: 413 | 3 我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
。。。。。。
yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
都想放弃刷题啦！
但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
，搞了3d table。晕啊！哪位大牛能解释一下呢？
如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
这个有recursion还比没有recursion的快！
class Solution {
private:
bool isDeformation(string &s1, string &s2)
{
if(s1.size() != s2.size())return false;
int albe[26] = {0};
for(int i = 0; i < s1.size(); i ++)
albe[s1[i]... 阅读全帖 |
|
m********c
发帖数: 105 | 4 贴一个我的recursive代码，time complexity是O(n^2)，large Judge用了144ms，不
是最优解，但是容易理解
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s1 == s2)
return true;
int size = s1.size();
int value1=0, value2=0;
for (int i=0; i
value1 += (s1[i]-'a');
value2 += (s2[i]-'a');
}
if (value1 != value2)
r... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 5 贴第二题：
import java.util.*;
public class Solution {
static Hashtable ht = new Hashtable();
static public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
String key = s1 + s2;
if(s1.compareTo(s2) > 0){
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 6
);
哈哈。我写了一个。跟你几乎一模一样。
HashMap hm = new HashMap();
public boolean isScramble(String s1, String s2)
{
if (s1 == null || s2 == null)
return false;
if (s1.length() != s2.length())
return false;
if (s1.equals(s2))
return true;
String key1 = s1 + ":" + s2;
String key2 = s2 + ":" + s1;
if (hm.containsKey(key1))
return hm.get(key1);
if (hm.containsKey(key... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 7 贴第二题：
import java.util.*;
public class Solution {
static Hashtable ht = new Hashtable();
static public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
String key = s1 + s2;
if(s1.compareTo(s2) > 0){
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 8
);
哈哈。我写了一个。跟你几乎一模一样。
HashMap hm = new HashMap();
public boolean isScramble(String s1, String s2)
{
if (s1 == null || s2 == null)
return false;
if (s1.length() != s2.length())
return false;
if (s1.equals(s2))
return true;
String key1 = s1 + ":" + s2;
String key2 = s2 + ":" + s1;
if (hm.containsKey(key1))
return hm.get(key1);
if (hm.containsKey(key... 阅读全帖 |
|
t**r
发帖数: 3428 | 9 这个解法好么？
1: bool isScramble(string s1, string s2) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(s1.size() != s2.size()) return false;
5: int A[26];
6: memset(A,0,26*sizeof(A[0]));
7: for(int i =0;i
8: {
9: A[s1[i]-'a']++;
10: }
11: for(int i =0;i
12: {
13: ... 阅读全帖 |
|
y****e
发帖数: 25 | 10 可以用recursion:
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) return false;
if (s1.equals(s2)) return true;
char []c1 = s1.toCharArray();
char []c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
if (!Arrays.equals(c1, c2)) return false;
for (int i = 1; i < s1.length(); i++) {
String s11 = s1.substring(0, i);
String s12 = s1.substring(i);
... 阅读全帖 |
|
O******i
发帖数: 269 | 11 if (isScramble(str1, str2 + (length - i), i)
&& isScramble(str1 + i, str2, length - i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1 + i, str2 + i, length - i))
return true; |
|
J****3
发帖数: 427 | 12 recursive的话 你是循环分割俩string 判断是不是分别是scramble string 吧
比如 isScramble(s1.subtr(0,i), s2.substr(0,i))&&isScramble(s1.substr(i, len
- i), s2.substr(i, len-i)) || isScramble(s1.substr(0, i), s2.substr(len - i,
i))&&isScramble(s1.substr(i, len-i), s2.substr(0, len - i));
这样你会重复计算， 用一个dp[len][s1_start][s2_start] 三维数组去存中间结果解决 |
|
O******i
发帖数: 269 | 13 if (isScramble(str1+i, str2+(length-i), i)) return true;
这里好像不对，应该有几种情形，象LZ那样的DP转移方程 |
|
j********e
发帖数: 1192 | 14 我没有说字符集相同就能scramble，字符集相同是必要条件，而不充分。
我的做法是，先找到一个位置i在s1,j在s2使得分割后的4个字符串两两
有相同的字符集（i=j 或者i=N-j)。然后接着对这2对字符串继续做同样
的事情连寻找分割位置。这样递归下去，如果有某对字符串无法找到分割
位置，则表示失败。否则，最后分隔最小的字符串只有一个字符。就可以
判断scramble成功。
问题是，如果有多个分割位置，是否任选一个都可以？如果必须测试每个可能的分割位置，那复杂度就不好说了。
下面是我的简单实现代码，通过了leetcode的online judge (包括judge large)。这段代码中会处理所有可能的分割位置。如果只选第一个可能的分割位置，有一个测试失败了。
#include
#include
#include
#include
using namespace std;
#define BITMAP_LEN 256
bool compare_char_set(const char *s1, con... 阅读全帖 |
|
B*******1
发帖数: 2454 | 15 My code
pass all the test on 1337 online judge.
bool isScrambleHelper(const string &s1, const string &s2, map
string>, bool> &myMap)
{
pair key = make_pair(s1, s2);
if (myMap.count(key) != 0) return myMap[key];
bool result = false;
if (s1 == s2) {
result = true;
} else if (s1.size() != s2.size() ) {
result = false;
} else {
for (int i = 1; i < s1.size(); i++) {
if ((isScrambleHelper(s1.substr(0, i), s2.substr(... 阅读全帖 |
|
j*****y
发帖数: 1071 | 16 二爷可否帮我看看这个 dp 的写法是不是有什么地方值得优化的 :)
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s2.length();
if(s1.length() != n)
{
return false;
}
bool dp[n][n][n]; // dp[i][j][k] means the scrambility of substring
of length k + 1 starting at s1[i] and s2[j];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
for(int k = 0; k < n; ++k)
dp[i][j][k] = false;
for(in... 阅读全帖 |
|
p*****2
发帖数: 21240 | 17 感觉罗嗦不少，你按照我的java代码改改试试？
public boolean isScramble(String s1, String s2)
{
int n=s1.length();
boolean[][][] dp=new boolean[n][n][n+1];
for(int i=n-1; i>=0; i--)
for(int j=n-1; j>=0; j--)
for(int k=1; k<=n-Math.max(i,j);k++)
{
if(s1.substring(i,i+k).equals(s2.substring(j,j+k)))
dp[i][j][k]=true;
else
{
for(in... 阅读全帖 |
|
