在C ++中形成字符串的最短方法

假设我们有一个字符串，我们可以通过删除一些字符（可能没有删除）来形成该字符串的子序列。因此，如果源和目标有两个字符串，我们必须找到源的子序列的最小数量，以使它们的串联等于目标。如果无法完成任务，则返回-1。因此，如果源是“ abc”，目标是“ abcbc”，那么输出将是2。

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

• 定义一个可能的字符串，它将s和t作为输入

• 创建映射m

• 对于s中的每个字符c，标记m [c]：= 1

• 对于t中的每个字符c，如果m [c]为0，则返回false

• 返回真

• 现在从主要方法中，执行以下操作-

• ssz：= s和tsz的大小：= t的大小

• 创建字符类型键和数组类型值的映射m

• 对于我在0到ssz范围内

• 将我插入m [s [i]]

• pre：= -1和ret：= 1

• 对于我在0到tsz范围内

• 将ret增加1，然后pre：= v [0]

• 如果m中不存在t [i]，则返回-1

• v：= m [t [i]]

• 设置i：= v中元素的索引，大于pre

• 如果我不在列表的末尾

• 否则pre：= v [i]

• 返回ret

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

示例

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

输出结果

2