ST算法(Sliding Window):A easy way to slove the substring problems

algorithm template to slove substring search problems

这是一个利用哈希思想解决字符串问题，特别是关于子字符串的问题的模版

方法描述: 怎样实现滑动窗口

Generally speaking a sliding window is a sub-list that runs over an underlying collection. I.e., if you have an array like[a b c d e f g h]a sliding window of size 3 would run over it like[a b c]  [b c d]    [c d e]      [d e f]        [e f g]          [f g h]

implement the template with java

public class Solution {    public List
    
      slidingWindowTemplateByHarryChaoyangHe(String s, String t) {        //init a collection or int value to save the result according the question.        List
     
       result = new LinkedList<>();        if(t.length()> s.length()) return result;                //create a hashmap to save the Characters of the target substring.        //(K, V) = (Character, Frequence of the Characters)        Map
      
        map = new HashMap<>();        for(char c : t.toCharArray()){            map.put(c, map.getOrDefault(c, 0) + 1);        }        //maintain a counter to check whether match the target string.        int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.                //Two Pointers: begin - left pointer of the window; end - right pointer of the window        int begin = 0, end = 0;                //the length of the substring which match the target string.        int len = Integer.MAX_VALUE;                 //loop at the begining of the source string        while(end < s.length()){                        char c = s.charAt(end);//get a character                        if( map.containsKey(c) ){                map.put(c, map.get(c)-1);// plus or minus one                if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).            }            end++;                        //increase begin pointer to make it invalid/valid again            while(counter == 0 /* counter condition. different question may have different condition */){                                char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer                if(map.containsKey(tempc)){                    map.put(tempc, map.get(tempc) + 1);//plus or minus one                    if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).                }                                /* save / update(min/max) the result if find a target*/                // result collections or result int value                                begin++;            }        }        return result;    }}
      
     
    

实现滑动窗口算法的c++模版

class Solution{public:    vector
    
      slidingWindowTemplate(string s,string p){        // define a vector store the result position        vector
     
       result;        // string not have anagram        if(s.size()
      
        hash_map;        //  hash map string p         for(auto &c:p)            map[p]++;        // use counter store the hash map size        int counter=map.size();        // define two pointer,point to the window boundary        int left=0,right=0;        // the substring length        int len=INT_MAX;        for(right
       
        0)                        counter++;                }                left++;            }        }        return result;    }}
       
      
     
    

最容易理解的版本

// 解决实际问题class Solution {public:    vector
    
      findAnagrams(string s, string p) {        vector
     
       pv(26,0), sv(26,0), res;        if(s.size() < p.size())           return res;        // fill pv, vector of counters for pattern string and sv, vector of counters for the sliding window        for(int i = 0; i < p.size(); ++i)        {            ++pv[p[i]-'a'];            ++sv[s[i]-'a'];        }        if(pv == sv)           res.push_back(0);        //here window is moving from left to right across the string.         //window size is p.size(), so s.size()-p.size() moves are made         for(int i = p.size(); i < s.size(); ++i)         {             // window extends one step to the right. counter for s[i] is incremented             ++sv[s[i]-'a'];                        // since we added one element to the right,             // one element to the left should be forgotten.             //counter for s[i-p.size()] is decremented            --sv[s[i-p.size()]-'a'];             // if after move to the right the anagram can be composed,             // add new position of window's left point to the result             if(pv == sv)                 res.push_back(i-p.size()+1);        }        return res;    }};
     
    

reference: