LeetCode 76

概述

​ 题目要求在一个字符串中找到包含另一个字符串所有字符（包括重复字符）的最短子序列

思路

• 子序列问题，考虑滑动窗口思想

  string minWindow(string s, string t) {
          int l1=s.length(),l2=t.length();  //获得字符串长度
      	//做准备，能想d
          vector<int> mp(128,0);
          for(int j=0;j<t.length();j++)
          	mp[t[j]]++;
  		int kind=l2;
  
          int i=0;	
      	//保存每次结果和最终结果
          int result=INT_MAX;
  		string str="";
  		string str2="";
          for(int j=0;j<l1;j++){
              //窗口滑动操作
          	str+=s[j];	//记录窗口目前数据
  			if(mp[s[j]]>0){		//窗口滑动对之后操作影响的记录
  				kind--;
  			}
  			mp[s[j]]--;
  			 
              while(kind==0){		//临界情况
              	
  				int ans=j-i+1;
  				str2=result>ans?str:str2;
  				result=result>ans?ans:result;
                  //窗口起始位置向前滑动对记录的影响
  				mp[s[i]]++;
  				if(mp[s[i]]>0){
  					kind++;
  				}
  				str.erase(0,1);
  				i++;
  				
              }
          }
          return str2;
      }

• 对于此题，也可以不用每次记录窗口中的字符串，因为最后可以得到最终窗口的起始、终止位置。

• 对于此题，还可优化，窗口起始位置可以不用每次只滑动一次，可以直接将窗口前面和目标字符串无关的位置全部移动后再做进一步判断