N*********6
发帖数: 4372 | 1 看到板上有网友报面经，往前翻翻发现大家讨论过很多次
小弟有几个问题
String a 长度 m
String b 长度 n
String c 长度 m+n
verify c 是不是a 和 b的interleaving
1. 这道题用DP的话时间上应该是O(m*n),空间上填2d table的话是O(m*n)
如果重复利用行的话可以到O(n)
2. 如果是Recursion的话复杂度是多少呢？我不理解的是如果c
当前字符和a的当前字符以及b的当前字符都一样的话，要分两路
去查找，当然第一路如果返回true的话第二路就没必要了，可是
一个比较极端的例子
a: aaaaa
b: aaaad
c: aaaadaaaaa
如果算法在遇到相同的字符是先假定是从a string来的，这个例子
就会非常time consuming，需要不停back tracking，请问这种情况
下recursion的复杂度是多少呢？
昨天在leetcode上用recursion发现small data可以过，large的
就超时了
3. 如果递归，我个人觉得不应该在开始比较字符串长度是否相等吧？
因为每次获取字符串长度都要O(m)或者O(n)的时间，应该假设这两个
长度是已知或者只在最开始的时候比较一次，大家觉得呢？ | e****e
发帖数: 418 | 2 1. Agree.空间 O(min(m, n))
2. Running time: (m+n)!/(m or n)!
3. Agree on 只在最开始的时候比较一次. | c****9
发帖数: 164 | 3 贴个过了测试的递归dp的code
class Solution {
public:
vector > map;
bool help(string& s1,string& s2,string& s3,int i, int j)
{
if(i+j==s3.size())
map[i][j]=true;
if(map[i][j]==1)
return true;
else if(map[i][j]==0)
return false;
if(i
{
if(help(s1,s2,s3,i+1,j))
map[i][j]=1 ;
else
map[i][j] = 0 ;
}
if(j
{
if(help(s1,s2,s3,i,j+1))
map[i][j] = 1 ;
else
map[i][j] = 0 ;
}
return map[i][j]==1;
}
bool isInterleave(string s1, string s2, string s3) {
vector tmp(s2.size()+1,-1);
vector > map2(s1.size()+1,tmp);
map = map2;
if(s1.size()+s2.size()!=s3.size())
return false;
else
return help(s1,s2,s3,0,0);
}
}; |
|
