字符串问题

字符串问题是数据结构与算法考查的重点：主要涉及滑动窗口，动态规划等问题的使用！

字符串1：最长回文串（简单逻辑）

int longestPalindrome(string s) {
      map<char,int>m;
      for(auto i:s){
          m[i]++;
      }
      int res=0;
      for(auto it:m){
          int v=it.second;
          res+=v/2*2;  //记录偶数个数
          if(res%2==0&&v%2==1) ++res;  //存在奇数+1
      }
      return res;
  }

字符串2：最长回文子串（动态规划）

思路逻辑五步走：(填表运算)
状态：dp[i][j]表示子串，S[i,j]是否为回文子串？
转移方程：dp[i][j]=(s[i]==s[j])&&dp[i+1][j-1]
边界条件：j-1-(i+1)+1<2 j-i<3
初始值：dp[i][i]=true; (逐层计算上三角)
输出：记录为true时，最大的长度与初始位置。

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
/*字符串  最长循环子串  动态规划*/
string longestPalindrome(string s) {
  if(s.size()<2) return s;
  int len=s.size();
  int begin_index=0;
  int maxlen=0;
  vector<vector<bool>>dp(len,vector<bool>(len,false));
  for(int i=0;i<len;i++){   /*初始化*/
      dp[i][i]=true;
  }
  for(int j=1;j<len;j++){   /*从左到右依次遍历*/
      for(int i=0;i<len;i++){
          if(s[i]!=s[j]) dp[i][j]=false;
          else{
              if(j-i<3){  /*边界条件*/
                  dp[i][j]=true;
              }
              else{
                  dp[i][j]=dp[i+1][j-1];  /*dp[i+1][j-1]在dp[i][j]之前获得*/
              }
          }
          if(dp[i][j]&&j-i+1>maxlen){    /*结果输出*/
              maxlen=j-i+1;
              begin_index=i;
          }
      }
  }
  return s.substr(begin_index,maxlen);
}
int main(){
  string s="abababab";
  string res=longestPalindrome(s);
  cout<<res<<endl;
  return 0;
}

字符串3：最长不重复子串（滑动窗口）

滑动窗口: l,r,res的选取与移动（左窗口，右窗口，输出接口+判断条件）

#include<iostream>
#include<map>
#include<string>
using namespace std;
/*字符串：最长不重复的子串  滑动窗口*/
string getsubstr(string str){
  if(str.size()<=1) return str;
  map<char,int>m;
  int l=0,r=0;
  string res;
  int maxLen = 0;
  while(r<str.size()){     //遍历至结束
      char h = str[r];
      m[h]++;
      r++;                 //提前加1
      while(m[h] > 1){     //保证窗口元素一直无重复元素
          m[str[l++]]--;
      }
      if(maxLen < r - l){
          maxLen = r - l;
          res = str.substr(l, r - l);
          //cout<<l<<" "<<r<<endl;
          //cout<<res<<endl;
      }
  }
  return res;
}
int main(){
  string str="abcbbabcd";
  string res=getsubstr(str);
  cout<<res<<endl;
  return 0;
}

字符串4：重复的DNA序列 (常规map的应用)

vector<string> findRepeatedDnaSequences(string s) {
      vector<string>res;
      int k=10;
      map<string,int>m;
      if(s.size()<=k) return res;
      for(int i=0;i<=s.size()-k;i++){
          m[s.substr(i,k)]++;
      }
      for(auto j:m){
          if(j.second>1) res.push_back(j.first);
      }
      return res;
}

字符串5：最小覆盖子串（滑动窗口）

注意int (s.size()) != s.size()

map<char,int>mt,ms;

  bool check(){
      for(auto &i:mt){
          if(ms[i.first]<i.second) return false;
      }
      return true;
  }

  string minWindow(string s, string t) {
      string res;
      if(s.size()<t.size()) return res;

      for(auto &i:t){
          mt[i]++;
      }

      int l=0,r=-1,lenmax=INT_MAX;
      int begin_index=-1;
     while (r < int(s.size())){ //注意转化为int
          if(mt.find(s[++r])!=mt.end()) ms[s[r]]++; /*第一个包含所有t的窗口*/
          while(check()&&l<=r){  /*剪枝操作*/
              if(r-l+1<lenmax){
                  lenmax=r-l+1;
                  begin_index=l;
              }
              if(mt.find(s[l])!=mt.end()) ms[s[l]]--;
              ++l;
          }
      } 
      return begin_index==-1?res:s.substr(begin_index,lenmax);

字符串6：字母异位词（map的灵活应用）

vector<vector<string>> groupAnagrams(vector<string>& strs) {
      vector<vector<string>>res;
      if(strs.size()<1) return res;
      map<string,vector<string>>m;
      for(auto i:strs){
          string s=i;
          sort(s.begin(),s.end());
          m[s].push_back(i);
      }
      for(auto j:m){
          res.push_back(j.second);
      }
      return res;
  }