j*****y
发帖数: 1071 | 1 s1, s2
dp[i, j, k] 表示 s1[i] 和 s2[j] 为起点的长度为 k的 substring 是 scramble
string
这么一来就是三维了 ? |
t****a
发帖数: 1212 | 2 现在的同学们贴题目是不是不太喜欢解释名词啊？这样没几个人能看懂题目吧。 |
p*****2
发帖数: 21240 | 3
http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
看过我写的代码了吗？
【在 j*****y 的大作中提到】
: s1, s2
: dp[i, j, k] 表示 s1[i] 和 s2[j] 为起点的长度为 k的 substring 是 scramble
: string
: 这么一来就是三维了 ?
|
l*****a
发帖数: 14598 | 4 这是面世圣经里的题目，说明你准备不到位
【在 t****a 的大作中提到】
: 现在的同学们贴题目是不是不太喜欢解释名词啊？这样没几个人能看懂题目吧。
|
j*****y
发帖数: 1071 | 5 二爷的博客打不开阿，可不可以在这里大致解释一下那个dp的变量是什么？
多谢 :)
【在 p*****2 的大作中提到】
:
: http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
: 看过我写的代码了吗？
|
p*****2
发帖数: 21240 | 6 dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
string。
有三种情况需要考虑：
1. 如果两个substring相等的话，则为true
2. 如果两个substring中间某一个点，左边的substrings为scramble string，
同时右边的substrings也为scramble string，则为true
3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为
scramble
string, 同时s1右边substring和s2左边的substring也为scramble
string，则为true |
j*****y
发帖数: 1071 | 7 多谢二爷， 我的思路和你是一样的。
只不过要生成一个三维的矩阵，感觉有点犯怵阿 :)
scramble
【在 p*****2 的大作中提到】
: dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
: string。
: 有三种情况需要考虑：
: 1. 如果两个substring相等的话，则为true
: 2. 如果两个substring中间某一个点，左边的substrings为scramble string，
: 同时右边的substrings也为scramble string，则为true
: 3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为
: scramble
: string, 同时s1右边substring和s2左边的substring也为scramble
: string，则为true
|
p*****2
发帖数: 21240 | 8
我以前也犯怵，所以一直没写。那天写了一下还行，一共也就13行代码。
【在 j*****y 的大作中提到】
: 多谢二爷， 我的思路和你是一样的。
: 只不过要生成一个三维的矩阵，感觉有点犯怵阿 :)
:
: scramble
|
j*****y
发帖数: 1071 | 9 多谢二爷 ：）
【在 p*****2 的大作中提到】
:
: 我以前也犯怵，所以一直没写。那天写了一下还行，一共也就13行代码。
|
l*******b
发帖数: 2586 | 10 这个好，学习了。想了好久也不会做
scramble
【在 p*****2 的大作中提到】
: dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
: string。
: 有三种情况需要考虑：
: 1. 如果两个substring相等的话，则为true
: 2. 如果两个substring中间某一个点，左边的substrings为scramble string，
: 同时右边的substrings也为scramble string，则为true
: 3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为
: scramble
: string, 同时s1右边substring和s2左边的substring也为scramble
: string，则为true
|
|
|
d**e
发帖数: 6098 | 11 面试圣经是哪本？
【在 l*****a 的大作中提到】
: 这是面世圣经里的题目，说明你准备不到位
|
w****x
发帖数: 2483 | 12 重点是看哪有重复计算，写递归的时候应该有种强烈的重复计算的感觉 |
h****n
发帖数: 1093 | 13 introduction to leetcode?
【在 d**e 的大作中提到】
: 面试圣经是哪本？
|
j*****y
发帖数: 1071 | 14 二爷你有没有比较recursive 和 dp 的时间区别，我刚才比较了一下，有点 confuse
跑那个large test cases
recursive 花了 36 milisec
dp 花了 216 milisec
dp 比 recursive 慢了 7倍阿。
看来 c++ 创建 3维的矩阵很慢？
scramble
【在 p*****2 的大作中提到】
: dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
: string。
: 有三种情况需要考虑：
: 1. 如果两个substring相等的话，则为true
: 2. 如果两个substring中间某一个点，左边的substrings为scramble string，
: 同时右边的substrings也为scramble string，则为true
: 3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为
: scramble
: string, 同时s1右边substring和s2左边的substring也为scramble
: string，则为true
|
p*****2
发帖数: 21240 | 15
我这里java bottom-up比top-down快了一倍
【在 j*****y 的大作中提到】
: 二爷你有没有比较recursive 和 dp 的时间区别，我刚才比较了一下，有点 confuse
: 跑那个large test cases
: recursive 花了 36 milisec
: dp 花了 216 milisec
: dp 比 recursive 慢了 7倍阿。
: 看来 c++ 创建 3维的矩阵很慢？
:
: scramble
|
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(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(s1[i] == s2[j])
dp[i][j][0] = true;
for(int k = 1; k < n; ++k)
for(int i = 0; i < n - k; ++i)
for(int j = 0; j < n - k; ++j)
{
if(s1.substr(i, k + 1) == s2.substr(j, k + 1))
{
dp[i][j][k] = true;
continue;
}
for(int l = 1; l < k + 1; ++l)
{
if(dp[i][j][l - 1] && dp[i + l][j +l][k - l])
{
dp[i][j][k] = true;
break;
}
if(dp[i][j + k + 1 - l][l - 1] && dp[i + l][j][k - l
])
{
dp[i][j][k] = true;
break;
}
}
}
return dp[0][0][n - 1];
}
};
【在 p*****2 的大作中提到】
:
: 我这里java bottom-up比top-down快了一倍
|
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(int l=1; l
{
if(dp[i][j][l] && dp[i+l][j+l][k-l] || dp[i][j+k
-l][l] && dp[i+l][j][k-l])
{
dp[i][j][k]=true;
break;
}
}
}
}
return dp[0][0][n];
} |
p*****2
发帖数: 21240 | 18 还有能不能把你的recursive code法上来看看。 |
j*****y
发帖数: 1071 | 19 多谢二爷，这是我的 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))
{
return true;
}
for(int end = start1; end < end1; ++end)
{
if(isScramble(s1, start1, end, s2, start2, start2 + (end -
start1)) && isScramble(s1, end + 1, end1, s2, start2 + (end - start1) + 1,
end2))
{
return true;
}
if(isScramble(s1, start1, end, s2, end2 - (end - start1), end2)
&& isScramble(s1, end + 1, end1, s2, start2, start2 + (end1 - end - 1)))
{
return true;
}
}
return false;
}
bool isScramble(string s1, string s2) {
return isScramble(s1, 0, s1.length() -1, s2, 0, s2.length() -1);
}
};
【在 p*****2 的大作中提到】
: 还有能不能把你的recursive code法上来看看。
|
p*****2
发帖数: 21240 | 20
s2
是不是因为你加了这段剪枝？
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;
}
【在 j*****y 的大作中提到】
: 多谢二爷，这是我的 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());
|
|
|
p*****2
发帖数: 21240 | 21 还有就是你能不能recursive再加一下cache优化一下，看看效果如何？ |
j*****y
发帖数: 1071 | 22 你的意思是说我的 recursive 的高效是因为这个？
【在 p*****2 的大作中提到】
: 还有就是你能不能recursive再加一下cache优化一下，看看效果如何？
|
p*****2
发帖数: 21240 | 23
不然你干掉试试。
【在 j*****y 的大作中提到】
: 你的意思是说我的 recursive 的高效是因为这个？
|
j*****y
发帖数: 1071 | 24 二爷我发现一个问题，考虑剪枝的话，这种情况 recursive 比 bottom-up dp 有效
recursive的话，当发现一个 substring不匹配的话，不用往下做了，
可是dp是 bottom up, dp 发现一个 substring不匹配的话，还得继续往上做，
我刚才试了一下 dp里面也考虑剪枝，速度还是跟不上 剪枝了的 recursive
【在 p*****2 的大作中提到】
:
: 不然你干掉试试。
|
H****s
发帖数: 247 | 25 你的程序再加个cache就是 DP 了， 因为根据二爷的定义，recursion ＋ cache 就是
DP 不过DP不仅仅是recursion + cache.
不过这个帖子真够经典的，又学到了一个新概念 "recursion branch trimming" 不知
这个概念官方叫法是什么， 谁知道哪本算法书里有讨论啊？
【在 j*****y 的大作中提到】
: 二爷我发现一个问题，考虑剪枝的话，这种情况 recursive 比 bottom-up dp 有效
: recursive的话，当发现一个 substring不匹配的话，不用往下做了，
: 可是dp是 bottom up, dp 发现一个 substring不匹配的话，还得继续往上做，
: 我刚才试了一下 dp里面也考虑剪枝，速度还是跟不上 剪枝了的 recursive
|
p*****2
发帖数: 21240 | 26
recursion是有这个优点呀。可以干掉不需要的计算。很多题其实都可以暴力＋剪枝来
完成的，没必要用dp
【在 j*****y 的大作中提到】
: 二爷我发现一个问题，考虑剪枝的话，这种情况 recursive 比 bottom-up dp 有效
: recursive的话，当发现一个 substring不匹配的话，不用往下做了，
: 可是dp是 bottom up, dp 发现一个 substring不匹配的话，还得继续往上做，
: 我刚才试了一下 dp里面也考虑剪枝，速度还是跟不上 剪枝了的 recursive
|
p*****2
发帖数: 21240 | 27
是
prunning把
【在 H****s 的大作中提到】
: 你的程序再加个cache就是 DP 了， 因为根据二爷的定义，recursion ＋ cache 就是
: DP 不过DP不仅仅是recursion + cache.
: 不过这个帖子真够经典的，又学到了一个新概念 "recursion branch trimming" 不知
: 这个概念官方叫法是什么， 谁知道哪本算法书里有讨论啊？
|
H****s
发帖数: 247 | 28 恩，还是二爷专业！ 工作中看到过函数是以这个单词命名的，现在算是理解啦。
【在 p*****2 的大作中提到】
:
: 是
: prunning把
|
H****s
发帖数: 247 | 29 恩，还是二爷专业！ 工作中看到过函数是以这个单词命名的，现在算是理解啦。
【在 p*****2 的大作中提到】
:
: 是
: prunning把
|
