问一道Google面经

好像只能brute force啊

likenisha 发表于 2016-1-22 22:59
two pointers,这个是原题咯

求问这个双指针怎么做？尤其是可能pattern还会有重复的char，这样感觉最少也要O( lenA * lenB )

韦斯特大人 发表于 2016-1-22 11:08
求问这个双指针怎么做？尤其是可能pattern还会有重复的char，这样感觉最少也要O( lenA * lenB )

看错题了，这个题是dp，我原来没看到保留顺序的

likenisha 发表于 2016-1-23 01:22
看错题了，这个题是dp，我原来没看到保留顺序的

soga 谢谢分享

Hotzenplotz 发表于 2016-1-21 07:36
暴力就是O(n^2):
遍历str1,如果某个char i和str2的第一个char相同，就从i开始往后遍历所有字符，直到找 ...

这是kmp吗？可以分享下代码吗？

就是strstr啊。。。另外应该是substring,不是subsequence

新宿车站 发表于 2016-3-5 14:20
就是strstr啊。。。另外应该是substring,不是subsequence

楼上看题不仔细，不是strstr, 也不是substring, 就是subsequence，题是没错的，这是一道DP的题

neverlandly 发表于 2016-3-6 03:41
楼上看题不仔细，不是strstr, 也不是substring, 就是subsequence，题是没错的，这是一道DP的题

string是要连续的，你要找的就是连续的。这就是substring。我看清你的题了

新宿车站 发表于 2016-3-6 09:31
string是要连续的，你要找的就是连续的。这就是substring。我看清你的题了

准确说，是从str1找substring，使得这个substring里有subsequence=str2

韦斯特大人 发表于 2016-1-23 00:08
求问这个双指针怎么做？尤其是可能pattern还会有重复的char，这样感觉最少也要O( lenA * lenB )

三个指针就可以了吧，复杂度还是O(lenA * lenB)