C++의 최소 창 부분 문자열

문자열 S와 T가 있다고 가정합니다. T의 모든 문자를 포함할 S의 최소 창을 찾아야 합니다. 따라서 입력이 "ABHDAXCVBAGTXATYCB" 및 T ="ABC"와 같으면 결과는 다음과 같습니다. CVBA”.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 지도 만들기 m

• x의 주파수를 m에 저장

• 길이 :=s의 크기, 왼쪽 :=0, 오른쪽 :=0, ansLeft :=0 및 ansRight :=0

• 카운터 :=x의 크기, 플래그 :=false, ans :=빈 문자열

• 동안 높이

  • c :=s[오른쪽]

  • c가 m에 있으면

    • m[c]> 0이면 카운터를 1로 줄입니다.

    • m[c] 1 감소

  • 카운터 =0 및 왼쪽 <=오른쪽

    동안

    • 오른쪽 – 왼쪽 + 1 <=길이

      인 경우

      • 길이 :=오른쪽 – 왼쪽 + 1

      • 플래그 :=참

      • ansLeft :=왼쪽, ansRight :=오른쪽

    • 왼쪽 =오른쪽이면 루프를 끊습니다.

    • c :=s[왼쪽]

    • c가 m에 있으면 m[c]를 1 증가

    • m[c]> 0이면 카운터를 1만큼 증가

    • 왼쪽으로 1 증가

  • 오른쪽으로 1 증가

• 플래그가 거짓이면 다음으로 반환

• 그렇지 않으면 ansLeft에서 ansRight 범위의 i에 대해 s[i]

  만큼 an을 증가시킵니다.

• 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minWindow(string s, string x) {
      map <char, int> m;
      for(int i =0;i<x.size();i++)m[x[i]]++;
      int length = s.size();
      int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
      int counter = x.size();
      bool flag = false;
      string ans = "";
      while(right<s.size()){
         char c = s[right];
         if(m.find(c)!=m.end()){
            if(m[c]>0)counter--;
            m[c]--;
         }
         while(counter == 0 && left<=right){
            if(right-left+1 <=length){
               length = right-left+1;
               flag = true;
               ansLeft = left;
               ansRight = right;
            }
            if(left == right)break;
            c = s[left];
            if(m.find(c)!=m.end()){
               m[c]++;
               if(m[c]>0)counter++;
            }
            left++;
         }
         right++;
      }
      if(!flag)return ans;
      else
      for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

입력

"ABHDAXCVBAGTXATYCB"
"ABC"

출력

CVBA