w******l
发帖数: 58 | 1 write a function that take a large string (i.e. abdacfd), and a small string
(i.e. ad), find the smallest
substring of the large string such that it cont
ains all characters in the small string(ans is da here). what is the complex
ity of algorithm? |
k***g
发帖数: 75 | |
c****s
发帖数: 241 | 3 不好意思，又看错题了。:(
【在 k***g 的大作中提到】
: 我觉得你理解错了题
:
: let
|
B*****t
发帖数: 335 | 4 二分+hash， 最坏的情况下复杂度O(nlogn), n is the length of the large string.
string
complex
【在 w******l 的大作中提到】
: write a function that take a large string (i.e. abdacfd), and a small string
: (i.e. ad), find the smallest
: substring of the large string such that it cont
: ains all characters in the small string(ans is da here). what is the complex
: ity of algorithm?
|
c****s
发帖数: 241 | 5 这个复杂度是O(mn)，优化查找的地方可以到O(n).
修了几个bug，:( 多谢blueant指出。
//no duplicate chars in small; case sensitive in all strings
void findSmallestSubstring(string large, string small){
int size = small.size()+1;
char lookupTable[256];
for( int i=0; i<256; i++) lookupTable[i] = 0;
//pTable[0] is useless;
int pTable[256];
for( int i=0; i<256; i++) pTable[i] = -1;
for(int i=0; i
lookupTable[small[i]] = i+1;
int start
【在 k***g 的大作中提到】
: 我觉得你理解错了题
:
: let
|
B*****t
发帖数: 335 | 6 I think there is a bug in your code, check this out
findSmallestSubstring2("abcpackmcb", "abc");
could you please give me 以前讨论过的 links 么？
thanks
要在
【在 c****s 的大作中提到】
: 这个复杂度是O(mn)，优化查找的地方可以到O(n).
: 修了几个bug，:( 多谢blueant指出。
: //no duplicate chars in small; case sensitive in all strings
: void findSmallestSubstring(string large, string small){
: int size = small.size()+1;
: char lookupTable[256];
: for( int i=0; i<256; i++) lookupTable[i] = 0;
: //pTable[0] is useless;
: int pTable[256];
: for( int i=0; i<256; i++) pTable[i] = -1;
|
c****s
发帖数: 241 | 7 多谢指出，我已经更正。
应该在：面试实录->google面试 里面的哪一个。具体的就不清楚了。:)
【在 B*****t 的大作中提到】
: I think there is a bug in your code, check this out
: findSmallestSubstring2("abcpackmcb", "abc");
: could you please give me 以前讨论过的 links 么？
: thanks
:
: 要在
|
B*****t
发帖数: 335 | 8 I am not good at searching, but thanks for your code anyway.
【在 c****s 的大作中提到】
: 多谢指出，我已经更正。
: 应该在：面试实录->google面试 里面的哪一个。具体的就不清楚了。:)
|
