資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告