C++에서 문자열을 형성하는 가장 짧은 방법

<시간/>

문자열이 있다고 가정하면 몇 개의 문자를 삭제하여 해당 문자열의 하위 시퀀스를 형성할 수 있습니다(삭제가 없을 수도 있음). 따라서 두 개의 문자열 소스와 대상이 있는 경우 연결이 대상과 같도록 소스의 하위 시퀀스의 최소 수를 찾아야 합니다. 작업이 불가능한 경우 -1을 반환합니다. 따라서 소스가 "abc"이고 대상이 "abcbc"이면 출력은 2가 됩니다.

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

가능하다는 문자열을 정의하십시오. 이것은 s와 t를 입력으로 받습니다.
지도 만들기 m
s mark m[c]의 각 문자 c에 대해 :=1
t의 각 문자 c에 대해 m[c]가 0이면 false를 반환합니다.
true를 반환
이제 주요 방법에서 다음을 수행하십시오 -
ssz :=s의 크기 및 tsz :=t의 크기
문자 유형 키 및 배열 유형 값의 맵 m 생성
범위 0에서 ssz까지의 i에 대해
- m[s[i]]에 i 삽입
pre :=-1 및 ret :=1
범위 0에서 tsz까지의 i에 대해
- t[i]가 m에 없으면 -1을 반환합니다.
- v :=m[t[i]]
- set i :=pre보다 큰 v의 요소 인덱스
- 내가 목록의 끝이 아닌 경우
  - ret를 1만큼 증가시키고 pre :=v[0]
- 그렇지 않으면 pre :=v[i]
리턴 렛

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

입력

"abc"
"abcbc"