C ++中的匹配子序列数

假设我们有一个字符串S和一个单词word的字典，请找到单词S的子序列[i]的数量。因此，如果输入为S =“ abcde”，而字典为[“ a”，“ bb”， “ acd”，“ ace”]，则输出为3。因为字典中存在三个单词序列，它们是S的子序列：“ a”，“ acd”和“ ace”

为了解决这个问题，我们将遵循以下步骤-

• n：=单词数组的大小

• 创建一张映射

• 对于我来说，范围是0至字数

• 在映射的m [words [i，0]]位置插入words [i]

• 回答：= 0

• 对于范围从0到S的i

• temp：= m [x]，然后删除m [x]

• 对于范围在0到临时大小之间的j

• 如果temp [j]的大小= 1，则将ans加1，否则将temp [j]的子字符串从索引1插入m [temp [j，1]]

• 字符x：= S [i]

• 如果在映射m中存在x，则

• 返回ans

让我们看下面的实现以更好地理解-

示例

#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