C++で一致するサブシーケンスの数

文字列Sと単語wordsの辞書があるとすると、Sのサブシーケンスであるwords [i]の数を見つけます。したがって、入力がS =“ abcde”で、辞書が[“ a”、“ bb”、 「acd」、「ace」]の場合、出力は3になります。辞書にはSのサブシーケンスである単語の3つのシーケンスがあるため、「a」、「acd」、「ace」

これを解決するには、次の手順に従います-

• n：=単語配列のサイズ
• 1つのマップを作成するm
• 0から単語のサイズまでの範囲のiの場合
  • words[i]をマップのm[words[i、0]]の位置に挿入します
• ans：=0
• 0からSのサイズまでの範囲のiの場合
  • char x：=S [i]
  • xがマップmに存在する場合、
    • temp：=m [x]、およびm [x]
    を削除します
    • 範囲0から一時サイズのjの場合
      • temp [j] =1の場合、ansを1増やします。それ以外の場合は、temp[j]のサブストリングをインデックス1からm[temp [j、1]]
      に挿入します。
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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"};

出力

3