c***g
发帖数: 472 | 1 Given a word (assume every char is unique in this word) and a string, find
the length of the shortest snippet/substring that contains all characters of
the word. For example: with word "abc" and the string "a brilliant cat is
eating a big cake", the shortest snippet is"big ca", which has length 6.
我能想到的是，用两个index，keep 一个window，然后滑动，每当找到一个substring
满足后，后面的index就滑到下一个可能的字母那里去。
请问谁有更好的方法么？ | k*****y
发帖数: 744 | 2 traverse一遍string，记当前位置是i；
用map pos记录word里面相应字母出现在i之前最后的位置；
如果word中每个字母都出现了，找出pos中位置最小的一个，就可以算出以i为结尾最短
的长度。
====================================
string getShortestSubstr(string &word, string &str) {
map pos;
int left, length=str.length()+1;
for( int i=0; i
char ch = str[i];
if( word.find(ch) != string::npos ) {
pos[ch] = i;
if( pos.size() == word.size() ){
int leftPos = i;
for( map::iterator iter=pos.begin();iter!=pos.end(
); ++iter )
if( iter->second < leftPos )
leftPos = iter->second;
if( i-leftPos+1 < length )
left = leftPos, length = i-leftPos+1;
}
}
}
string substr;
if( pos.size() == word.size() )
substr = str.substr(left, length);
return substr;
}
of
substring
【在 c***g 的大作中提到】
: Given a word (assume every char is unique in this word) and a string, find
: the length of the shortest snippet/substring that contains all characters of
: the word. For example: with word "abc" and the string "a brilliant cat is
: eating a big cake", the shortest snippet is"big ca", which has length 6.
: 我能想到的是，用两个index，keep 一个window，然后滑动，每当找到一个substring
: 满足后，后面的index就滑到下一个可能的字母那里去。
: 请问谁有更好的方法么？
| q******8
发帖数: 848 | | h********e
发帖数: 1972 | 4 two pointers with a counter of sizer 26, O(n) time. |
|
