c********t
发帖数: 5706 | 1 昨天做了道challenge的题，输入两个String, a and b, 要求返回能够满足（
subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
我的做法代码复杂而且时间
复杂度也感觉不好。为了不误导大家，大牛先试试有没有好的解法，我再抛砖。 | h******k
发帖数: 810 | | l****u
发帖数: 1764 | 3 subsequance 和substring有什么区别？
如果是longest common substring，好像是用二维dp来解？ | c********t
发帖数: 5706 | 4 这样说来dp可以解决？但我遇到的是不是2 substring match, 是subsequence matches
substring。
2 substring match f(i,j)=f(i-1)(j-1)+1
subsequence matches substring, 难道要遍历row（i-1)? f(i,j)=Max(f(i-1,0)...
.f(i-1,j-1))+1
这样一来就是O(m*n*n)了，与dfs没区别了。
不过好像每个row去掉所有0，都是递增序列，可能可以找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0).
如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。
【在 h******k 的大作中提到】
: 这个？
: https://en.m.wikipedia.org/wiki/Longest_common_substring_problem
: 面试要问这个，多半是来找茬的。
| c********t
发帖数: 5706 | 5 Subsequence 是指可以删除任意一些characters后的string (保持原顺序）
https://en.wikipedia.org/wiki/Subsequence
【在 l****u 的大作中提到】
: subsequance 和substring有什么区别？
: 如果是longest common substring，好像是用二维dp来解？
| c********t
发帖数: 5706 | 6 试了一下DP，一维array记录所有row最大值不行，必须找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了，最坏情况是b里很多duplicate,
O(m*n*n)。
matches
..
x
【在 c********t 的大作中提到】
: 这样说来dp可以解决？但我遇到的是不是2 substring match, 是subsequence matches
: substring。
: 2 substring match f(i,j)=f(i-1)(j-1)+1
: subsequence matches substring, 难道要遍历row（i-1)? f(i,j)=Max(f(i-1,0)...
: .f(i-1,j-1))+1
: 这样一来就是O(m*n*n)了，与dfs没区别了。
: 不过好像每个row去掉所有0，都是递增序列，可能可以找最后的值 f(i,j) = f(i-1, x
: ) ( x=max(0, j-1) and f(i-1, x)>0).
: 如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。
| c********t
发帖数: 5706 | 7 今天返回来一看这题，马上O(m*n) dp写出了。状态太重要了。
x
search,
duplicate,
【在 c********t 的大作中提到】
: 试了一下DP，一维array记录所有row最大值不行，必须找最后的值 f(i,j) = f(i-1, x
: ) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
: O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了，最坏情况是b里很多duplicate,
: O(m*n*n)。
:
: matches
: ..
: x
|
|
