在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