滑动窗口

8.Permutation in a String (hard) 问题描述

给定一个字符串和一个模式，找出该字符串是否包含模式的任何排列。

排列被定义为字符串中字符的重新排列。

例如，“abc”有以下六个排列：
abc
acb
bac
bca
cab
cba
Example 1:

Input: String="oidbcaf", Pattern="abc"
Output: true
Explanation: The string contains "bca" which is a permutation of the given pattern.

Example 2:

Input: String="bcdxabcdy", Pattern="bcdyabcdx"
Output: true
Explanation: Both the string and the pattern are a permutation of each other.

Example 3:

Input: String="bcdxabcdy", Pattern="bcdyabcdx"
Output: true
Explanation: Both the string and the pattern are a permutation of each other.

Example 4:

Input: String="aaacb", Pattern="abc"
Output: true
Explanation: The string contains "acb" which is a permutation of the given pattern.

解题的关键：

1.首先patten的给出就已经明显的提示大家了，窗口的大小固定，所以窗口得在窗口尾巴位置大于等于pattern长度时收缩，以保持窗口的大小不变。

2.要做的就是检查一下窗口内的字符是否是pattern一种排列。

这需要借助数据结构，我觉得map和unordered_map都可，用map会好写一点，首先先把pattern的字符放入map，再把窗口内的字符放入另一个map，由于map具有自动排序的功能，所以若是二者互为重新排列，两个map是相同的。

用unordered_map会省空间一点，你需要记录窗口内每个字符的出现频率，来实现。

bool permutation(string str,string patten)
{
    int winstat = 0;
    bool res =false;
    map<char,int> pat;
    map<char,int> map;
    for(int i = 0;i<patten.size();++i)
    {
        pat[patten[i]]++;//pattern的map初始化
    }
    for(int winend=0;winend<str.size();++winend)
    {

        map[str[winend]]++;
        if(winend >= patten.size()-1)//收缩是为了保持窗口的大小
        {
            if(pat == map) return true;//比较两个map
            map[str[winstat]]--;
            if(map[str[winstat]] == 0)
            {
                map.erase(str[winstat]);
            }
            winstat++;
        }
        
    }
    return false;
}

9.String Anagrams (hard) 问题描述

给定一个字符串和一个模式，找到给定字符串中模式的所有相同字母异序词。

每个相同字母异序词都是一个字符串的排列。

众所周知，当我们在寻找字符串的排列时不允许重复字符时，我们得到 N！个相同字母异序词

排列被定义为字符串中字符的重新排列。

例如，“abc”有以下六个排列：
abc
acb
bac
bca
cab
cba
Example 1:

Input: String="ppqp", Pattern="pq"
Output: [1, 2]
Explanation: The two anagrams of the pattern in the given string are "pq" and "qp".

Example 2:

Input: String="abbcabc", Pattern="abc"
Output: [2, 3, 4]
Explanation: The three anagrams of the pattern in the given string are "bca", "cab", and "abc".

解题的关键：

1.和上题思路一模一样，只需要将所有相同字母异序词都找出即可

vector<int> permutation(string str,string patten)
{
    int winstat = 0;
    vector<int> res;
    map<char,int> pat;
    map<char,int> map;
    for(int i = 0;i<patten.size();++i)
    {
        pat[patten[i]]++;
    }
    for(int winend=0;winend<str.size();++winend)
    {

        map[str[winend]]++;
        if(winend >= patten.size()-1)
        {
            if(pat == map) res.emplace_back(winstat);//找出所有符合题意的解
            map[str[winstat]]--;
            if(map[str[winstat]] == 0)
            {
                map.erase(str[winstat]);
            }
            winstat++;
        }
        
    }
    return res;
}

10.Smallest Window containing Substring (hard)# 问题描述

给定一个字符串和一个模式，找到给定字符串中包含给定模式的所有字符出现的最小子字符串。

Example 1:

Input: String="aabdec", Pattern="abc"
Output: "abdec"
Explanation: The smallest substring having all characters of the pattern is "abdec"

Example 2:

Input: String="aabdec", Pattern="abac"
Output: "aabdec"
Explanation: The smallest substring having all character occurrences of the pattern is "aabdec"

Example 3:

Input: String="abdbca", Pattern="abc"
Output: "bca"
Explanation: The smallest substring having all characters of the pattern is "bca".

Example 4:

Input: String="adcad", Pattern="abc"
Output: ""
Explanation: No substring in the given string has all characters of the pattern.

1.显然窗口大小是在变化的,我们要让pattern中所有字母出现在窗口中，然后s使得窗口扩大或收缩得到一个最小的窗口大小。

2.需要unordered_map来记录字符出现的次数，还需要一个变量来记录窗口中出现pattern中字符的个数。

string findSubstring(const string &str, const string &pattern) {
    int windowStart = 0, matched = 0, minLength = str.length() + 1, subStrStart = 0;
    unordered_map<char, int> charFrequencyMap;
    for (auto chr : pattern) {
      charFrequencyMap[chr]++;
    }
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) 
    {
      char rightChar = str[windowEnd];
      if (charFrequencyMap.find(rightChar) != charFrequencyMap.end()) 
      {//注意这个括号，必须在map中找到这个字符才能增加匹配个数，两个条件都要满足
        charFrequencyMap[rightChar]--;
        if (charFrequencyMap[rightChar] >= 0) {  
          matched++;
        }
      }

      // 当满足窗口内出现所有pattern内的字母时就可以收缩
      while (matched == pattern.length()) {
        //更新长度
        if (minLength > windowEnd - windowStart + 1) {
          minLength = windowEnd - windowStart + 1;
          subStrStart = windowStart;
        }

        char leftChar = str[windowStart++];
        if (charFrequencyMap.find(leftChar) != charFrequencyMap.end()) {
         //收缩时根据移除出窗口的字符来跟新匹配次数和map内的出现次数
          if (charFrequencyMap[leftChar] == 0) {
            matched--;
          }
          charFrequencyMap[leftChar]++;
        }
      }
    }

    return minLength > str.length() ? "" : str.substr(subStrStart, minLength);
  }