f514 - 拼字遊戲 (Spelling)

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩個字串 a 和 b，要求對於 b 中的每個字元，在 a 中找到第一個相同字元的位置，並輸出該位置的索引（從 1 開始）。如果 b 中的字元在 a 中不存在，則輸出 "X"。

解題思路

這題的解題思路是對於字串 b 中的每個字元，遍歷字串 a，尋找第一個匹配的字元。如果找到匹配的字元，則輸出其在 a 中的索引，並將 a 中該字元替換為空格，以避免重複匹配。如果遍歷完 a 仍未找到匹配的字元，則輸出 "X"。這是一個簡單的貪婪演算法，每次都嘗試找到第一個匹配的字元。

複雜度分析

• 時間複雜度: O(m*n)，其中 n 是字串 a 的長度，m 是字串 b 的長度。因為對於字串 b 中的每個字元，都需要遍歷字串 a。
• 空間複雜度: O(1)，因為只使用了常數額外的空間。

程式碼

#include <iostream>
using namespace std;
string a,b;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> a >> b;
	int al=a.length(),bl=b.length();
	for(int i=0;i<bl;++i){
		int s=0;
		for(int j=0;j<al;++j){
			if(b[i]==a[j]){
				cout << j+1 << " ";
				a[j]=' ';
				s=1;
				break;
			}
		}
		if(s==0){
			cout << "X "; 
		}
	}
}