数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中最短的字符串形成方法
假设我们有一个字符串，我们可以通过删除一些字符（可能不删除任何字符）来形成该字符串的子序列。因此，如果存在两个字符串 source 和 target，我们必须找到 source 的子序列的最小数量，使得它们的连接等于 target。如果任务不可能完成，则返回 -1。例如，如果 source 是“abc”而 target 是“abcbc”，则输出为 2。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 possible 的字符串，它将接收 s 和 t 作为输入
创建一个映射 m
对于 s 中的每个字符 c，将 m[c] 设置为 1
对于 t 中的每个字符 c，如果 m[c] 为 0，则返回 false
返回 true
现在从主方法中执行以下操作：
ssz := s 的大小，tsz := t 的大小
创建一个字符类型键和数组类型值的映射 m
对于 i 从 0 到 ssz
将 i 插入 m[s[i]]
pre := -1，ret := 1
对于 i 从 0 到 tsz
如果 t[i] 不存在于 m 中，则返回 -1
v := m[t[i]]
设置 i := v 中大于 pre 的元素的索引
如果 i 不是列表的末尾
将 ret 加 1，pre := v[0]
否则 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
更新于：2020年4月30日
257 次查看
广告