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把
|