e854 - 拼字問題

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩個字串，一個是賀年卡上的字串 L，另一個是李先生剪下的字母字串。要求找出李先生能從 L 的第一個字開始拼出多少字。

解題思路

這個問題可以使用貪心演算法解決。首先，統計李先生剪下的字母字串中每個字母的出現次數。然後，遍歷賀年卡上的字串 L，如果當前字母在李先生的字母字串中存在，且數量大於 0，則將該字母輸出，並將李先生字母字串中對應字母的數量減 1。如果遇到賀年卡上的字母在李先生的字母字串中不存在，或者數量為 0，則停止輸出。

複雜度分析

• 時間複雜度: O(m + n)，其中 m 是賀年卡字串 L 的長度，n 是李先生剪下的字母字串的長度。
• 空間複雜度: O(1)，因為字母的數量是固定的（26 個大寫字母），所以使用的空間是常數級別。

程式碼

#include <iostream>
using namespace std;
string a,b;
int c[26];
int main(){
	getline(cin,a);
	getline(cin,b);
	int al=a.length(),bl=b.length();
	for(int i=0;i<bl;++i)
		if(b[i]>='A')
			++c[b[i]-'A'];
	for(int i=0;i<al;++i){
		if(a[i]>='A'&&c[a[i]-'A'])
			--c[a[i]-'A'];
		else if(a[i]>='A'&&c[a[i]-'A']==0)
			break;
		cout << a[i];
	}
}