字串問題有個(gè)通用的滑動(dòng)窗口算法，時(shí)間復(fù)雜度O(n2)
其中關(guān)鍵：
- 窗口大小不固定：構(gòu)造合適的count來控制窗口的滑動(dòng)与倡。
- 窗口大小固定：使用left滩愁、right控制窗口移動(dòng)虫给。
- 使用HashTable控制記錄字符出現(xiàn)情況藤抡。（不在t中字符，或者已出現(xiàn)的應(yīng)該<= 0抹估，在t中的字符應(yīng)該>=0）
- 若存在待比較字符串t杰捂，則初始化HashTable（t中字符對(duì)應(yīng)value大于0），同時(shí)right++,HashTable中value--棋蚌，count代表未命中字符個(gè)數(shù)嫁佳。若無，則HashTable全部為0谷暮，同時(shí)right++蒿往，HashTable中value++，count++湿弦，count代表不同字符個(gè)數(shù)或者重復(fù)字符個(gè)數(shù)瓤漏。
int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one head
int d; //the length of substring
for() { /* initialize the hash map here */ }
while(end<s.size()){
if(map[s[end++]]-- ?){ /* modify counter here */ }
while(/* counter condition */){
/* update d here if finding minimum*/
//increase begin to make it invalid/valid again
if(map[s[begin++]]++ ?){ /*modify counter here*/ }
}
/* update d here if finding maximum*/
}
return d;
}
相關(guān)問題，76/242/438/159/3/30/340/395/467
解析: 2段字符串颊埃，找出包含t的最小窗口
邊界：s比t小
思路：count代表未命中的字符蔬充，移動(dòng)right和left，找出count為0時(shí)班利，最小的窗口饥漫。時(shí)間復(fù)雜度O(nm)
// 10行的滑動(dòng)窗口代碼模板
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--; //in t
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);
}
解析: 2段字符串，它們的內(nèi)容全部相同罗标，只是順序不同
邊界：長度不一致庸队，包含char個(gè)數(shù)不同
思路：使用排序O(nlog(n)),使用HashTable O(n)
// C++ map利用滑動(dòng)窗口思想
class Solution242 {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) {
return false;
}
if (s == t) {
return true;
}
vector<int> hash_map(128,0);
for (auto c : t) {
++hash_map[c];
}
int count = t.size(), left = 0, right = 0;
while (right < s.size()) {
if(--hash_map[s[right++]] >= 0) {
--count;
}
if(count == 0) {
return true;
}
}
return false;
}
};
解析: 242的升級(jí)版。2段字符串闯割，找出字符串A中所有可能是與字符串B構(gòu)成回文結(jié)構(gòu)的下標(biāo)彻消。設(shè)s長度為n,p長度為m
邊界：字符串大小為空，字符串A的大小 < 字符串B的大小
誤區(qū)：繼續(xù)按照242的套路宙拉，時(shí)間復(fù)雜度最小也是O(nm)
思路：使用滑動(dòng)窗口宾尚，窗口大小為m，滑動(dòng)n次谢澈，時(shí)間復(fù)雜度為O(n)煌贴。hash_map:使用p中字符出現(xiàn)次數(shù) 初始化該map。count:只會(huì)對(duì)hash中字符未命中的個(gè)數(shù)澳化；每次遍歷right++崔步，對(duì)應(yīng)的hash--；如果窗口大于hash缎谷，left++，對(duì)應(yīng)hash++×辛郑可以看出不在hash中的字符對(duì)應(yīng)的hash小于等于0（不會(huì)影響count）瑞你，而在hash中的字符對(duì)應(yīng)的hash開始就大于0。所以實(shí)際影響count的就是(left,right)區(qū)間內(nèi)的字符希痴，right經(jīng)過但left未經(jīng)過者甲，這些字符全部減-1，若此時(shí)hash>0的個(gè)數(shù)代表著初始化的hash正好被right移動(dòng)時(shí)減掉了砌创。
簡單解釋：利用了滑動(dòng)窗口的特性---右邊經(jīng)過的虏缸，左邊也會(huì)經(jīng)過。所以嫩实，右借左還刽辙，不會(huì)影響初始的結(jié)束條件。
時(shí)間復(fù)雜度O(n)
//
class Solution438 {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
vector<int> hash_map(128,0);
for (auto c : p) {
++hash_map[c];
}
int count = p.size(), left = 0, right = 0;
while (right < s.size()) {
if(--hash_map[right++] >= 0) {
--count;
}
if(count == 0) {
result.push_back(left);
}
if((right - left) == p.size() && ++hash_map[left++] > 0) {
++count;
}
}
return result;
}
}
159. Longest Substring with At Most Two Distinct Characters
解析: 找出最多包含2個(gè)字符的最長子串甲献。
邊界：字符串長度小于3時(shí)宰缤，直接返回該字符串長度。
思路：count此處記錄不同的字符個(gè)數(shù)晃洒，count > 2時(shí)慨灭，為invalid的情況。
時(shí)間復(fù)雜度O(n2)
int lengthOfLongestSubstringTwoDistinct(string s) {
vector<int> hash_map(128,0);
int counter = 0, left = 0, right = 0, d = 0;
while (right < s.size()) {
if (hash_map[s[right++]]++ == 0) {
++counter;
}
while(counter > 2) {
if(--hash_map[s[left++]] == 0) {
--counter;
}
}
d = max(d, right - left);
}
return d;
}
解析: 找出字符不重復(fù)的最長子串球及。
邊界：字符串長度小于2時(shí)氧骤，直接返回該字符串長度。
思路：count此處記錄重復(fù)字符個(gè)數(shù)吃引，count為1時(shí)语淘，為invalid的情況，需要移動(dòng)left际歼。
時(shí)間復(fù)雜度O(n2)
int lengthOfLongestSubstring(string s) {
if (s.size() < 2) {
return s.size();
}
vector<int> hash_map(128, 0);
int count = 0, left = 0, right = 0, d = 0;
while (right < s.size()) {
if (hash_map[s[right++]]++ == 1) {
++count;
}
while (count == 1) {
if (--hash_map[s[left++]] == 1) {
--count;
}
}
d = max(d, right - left);
}
return d;
};
最優(yōu)算法的時(shí)間復(fù)雜度為O(n)惶翻，使用HashTable記錄字符最靠右的位置
int lengthOfLongestSubstring(string s) {
if(s.size() < 2) {
return s.size();
}
vector<int> hash_map(256,-1);
int left = 0, right = 0, d = 0;
while (right < s.size()) {
if (hash_map[s[right]] >= left) {
left = hash_map[s[right]] + 1;
}
hash_map[s[right]] = right++;
d = max(d, right - left);
}
return d;
};
解析: 找出包含列表中全部的字符串的起始位置集合，類似438鹅心。
邊界：s的大小小于列表長度吕粗。
思路：滑動(dòng)窗口，left依次劃過每個(gè)字符旭愧，判讀left-right之間的字符串是否全部與列表命中颅筋。
時(shí)間復(fù)雜度O(mn)
bool concatenation(string input, unordered_map<string, int> hash_table,int len) {
int length = len;
for (int i = 0; i < input.size()/len; ++i) {
if (--hash_table[input.substr(i*length, length)] < 0) {
return false;
}
}
for (unordered_map<string, int>::iterator it = hash_table.begin(); it != hash_table.end(); ++it) {
if (it->second != 0) {
return false;
}
}
return true;
}
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (words.size() == 0 || s.size() < (words[0].size())*words.size()) {
return result;
}
int length = words[0].size();
unordered_map<string,int> hash_table;
for (string word : words) {
hash_table[word]++;
}
for (int i = 0; i < s.size() - length + 1; ++i) {
if (concatenation(s.substr(i, words.size()*length), hash_table, length)) {
result.push_back(i);
}
}
return result;
}
解析: 找出每個(gè)字符最少重復(fù)K次的最長字符串。
邊界：子串長度小于K
思路：將字符串按字符詞典中小于K進(jìn)行劃分输枯，若字符詞典中出現(xiàn)次數(shù)全部大于K议泵，則返回該字符串長度，并遞歸執(zhí)行桃熄。
時(shí)間復(fù)雜度O(nlogn)
int longestSubstring(string s, int k) {
if (s.size() < k) {
return 0;
}
unordered_map<char,int> hash_map;
for (char c : s) {
hash_map[c]++;
}
set<char> splits;
for (unordered_map<char, int>::iterator it = hash_map.begin(); it != hash_map.end(); ++it) {
if (it ->second < k) {
splits.insert(it->first);
}
}
if (splits.size() == 0) {
return s.size();
}
else if (splits.size() == hash_map.size()) {
return 0;
}
vector<int> splits_loc;
for (int i = 0; i < s.size(); ++i) {
if (splits.find(s[i]) != splits.end()) {
splits_loc.push_back(i);
}
}
vector<int> result;
int left = 0, right = -1;
for (int loc : splits_loc) {
left = right + 1;
right = loc;
result.push_back(longestSubstring(s.substr(left,right-left),k));
}
result.push_back(longestSubstring(s.substr(left+1, s.size() - 1 - left), k));
return *(std::max_element(std::begin(result),std::end(result)));
}
解析: 連續(xù)字符的最大組合個(gè)數(shù)
邊界：不連續(xù)是組合個(gè)數(shù)為單個(gè)的
思路：有n個(gè)連續(xù)的就有 (1+2+3+...+n)種組合情況先口，額外加入不連續(xù)的字符個(gè)數(shù)即可。同時(shí)要考慮，兩段連續(xù)字符可能有部分重合的情況（這時(shí)候選取長的）碉京。
時(shí)間復(fù)雜度O(nlogn)
int findSubstringInWraproundString(string p) {
vector<int> letters(26,0);
int res = 0, len = 0;
for (int i = 0; i < p.size(); ++i) {
int cur = p[i] - 'a';
if (i > 0 && p[i-1] != (cur + 26 - 1) % 26 + 'a') {
len = 0;
}
if(++len > letters[cur]) {
res += len - letters[cur];
letters[cur] = len;
}
}
return res;
}
