C++에서 일치하는 부분 시퀀스의 수

<시간/>

문자열 S와 단어 사전이 있다고 가정하고 S의 하위 시퀀스인 단어[i]의 수를 찾으십시오. 따라서 입력이 S="abcde"이고 사전이 ["a", "bb"이면, "acd", "ace"], 출력은 3이 됩니다. 사전에 단어의 세 시퀀스가 있기 때문에 S의 하위 시퀀스인 "a" "acd" 및 "ace"

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

n :=단어 배열의 크기
하나의 지도 만들기 m
0에서 단어 크기까지 범위에 있는 i의 경우
- 단어[i]를 지도 m[단어[i, 0]] 위치에 삽입
ans :=0
0에서 S
- 문자 x :=S[i]
- 맵 m에 x가 있으면
  - temp :=m[x], m[x] 삭제
  - 0에서 임시 크기까지 범위에 있는 j의 경우
    - temp[j]의 크기가 1이면 ans를 1만큼 증가시키고, 그렇지 않으면 인덱스 1에서 m[temp[j, 1]]에 temp[j]의 하위 문자열을 삽입합니다.
반환

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numMatchingSubseq(string S, vector<string>& words) {
      int n = words.size();
      map <char, vector <string> > m;
      for(int i = 0; i < words.size(); i++){
         m[words[i][0]].push_back(words[i]);
      }
      int ans = 0;
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         if(m.find(x) != m.end()){
            vector <string> temp = m[x];
            m.erase(x);
            for(int j = 0; j < temp.size(); j++){
               if(temp[j].size() == 1){
                  ans++;
               } else {
                  m[temp[j][1]].push_back(temp[j].substr(1));
               }
            }
         }
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   string s = "abcde";
   vector<string> v{"a","bb","acd","ace"};
   cout << ob1.numMatchingSubseq(s, v) << endl;
   return 0;
}

입력

"abcde"
["a","bb","acd","ace"]
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};