注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
总结下求一个字符串中的子字符串问题模版:
int findSubstring(string s){ vector<int> map(128,0); int counter; int begin=0, end=0; int d; /子序列的长度 for() { /* 初始化表 如果需要的话 想76需要 3就不需要*/} while(end<s.size()){ if(map[s[end++]]-- ?){ /* modify counter here */ } while(/* counter condition */){ if(map[s[begin++]]++ ?){ /*modify counter here*/ } } /* update d here if finding maximum*/ } return d; }example:
76:
string minWindow(string s, string t) { vector<int> map(128,0); for(auto c: t) map[c]++; int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0; while(end<s.size()){ if(map[s[end++]]-->0) --counter; while(counter==0){ //valid if(end-begin<d) d=end-(head=begin); if(map[s[begin++]]++==0) ++counter; //make it invalid } } return d==INT_MAX? "":s.substr(head, d); }3:int lengthOfLongestSubstring(string s) { vector<int> map(128,0); int begin =0, end =0, d =0, head =0; int counter =0; while(end<s.size()){ if(map[s[end++]]++ >0){counter ++;} while(counter>0){ if(map[s[begin++]]-->1) counter --; } d = max(d, end-begin); } return d; }或者google 面试题给了一个char set t: {a, b, c},再给一个 string s: "abccddabcd" 最早出现包含abc的位置vector<int> map(128,0);
string s = "abccddabcd";
string t = "abcd";
int begin = 0, end =0, d =INT_MAX, counter =t.size();
int head;
for(int i=0; i<t.size();i++){
map[t[i++;
}
while(end<s.size()){
if(map[s[end++-->0) {
--counter;
}
while(counter==0){
if(end-begin<d)
d = end-(head=begin);
if(d == t.size()) {cout<<head<<endl; return 0;}
if(map[s[begin++++==0) {
counter++;
}
}
}
|