e624 - 10340 - All in All
題目描述
題目要求判斷字串 s 是否為字串 t 的子序列。換句話說，是否可以從 t 中刪除一些字元，使得剩下的字元組成 s。
解題思路
使用貪心演算法。遍歷字串 s 的每個字元，並在字串 t 中尋找該字元的下一個出現位置。如果找到，則將 s 的當前字元標記為已匹配（例如，替換為 '0'），並繼續尋找 s 的下一個字元。如果在 t 中找不到 s 的當前字元，則 s 不是 t 的子序列，輸出 "No"。如果成功匹配 s 的所有字元，則輸出 "Yes"。
複雜度分析
- 時間複雜度: O(m*n)，其中 m 是字串 s 的長度，n 是字串 t 的長度。最壞情況下，對於 s 的每個字元，我們可能需要遍歷 t 的所有字元。
- 空間複雜度: O(1)，因為我們只使用了常數額外的空間。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b;
while(cin >> a >> b){
int al=a.length(),bl=b.length();
for(int i=0,j=0,k=0;i<al;i++){
for(k=j;k<bl;k++){
if(a[i]==b[k]){
a[i]='0';
break;
}
}
j=k+1;
if(a[i]!='0'){
cout << "No\n" ;
break;
}
}
if(a[al-1]=='0')
cout << "Yes\n";
}
}