e507 - 10252 - Common Permutation

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出兩個字串 a 和 b 的最長公共子序列，且該子序列的字母可以重新排列。換句話說，我們要找到一個字串 x，它既是 a 的子序列，也是 b 的子序列，並且 x 的長度最大，且字母順序由小到大排列。

解題思路

解題思路是先對兩個字串 a 和 b 進行排序。然後使用兩個指標 i 和 j 分別遍歷排序後的 a 和 b。

• 如果 a[i] > b[j]，則 j 向右移動，因為 b[j] 不可能在 a 中找到匹配。
• 如果 a[i] == b[j]，則將 a[i] (或 b[j]) 添加到結果字串 ans 中，並且 i 和 j 都向右移動。
• 如果 a[i] < b[j]，則 i 向右移動，因為 a[i] 不可能在 b 中找到匹配。 這個過程持續到其中一個指標到達字串的末尾。

由於字串已經排序，因此找到的公共子序列自然是字母順序最小的。

複雜度分析

• 時間複雜度: O(n log n + m log m + n + m)，其中 n 和 m 分別是字串 a 和 b 的長度。排序需要 O(n log n) 和 O(m log m)，而雙指標遍歷需要 O(n + m)。
• 空間複雜度: O(min(n, m))，最壞情況下，結果字串 ans 的長度等於較短字串的長度。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	string a,b;
	while(getline(cin,a)){
		getline(cin,b);
		sort(a.begin(),a.end());
		sort(b.begin(),b.end());
		string ans;
		for(int i=0,j=0,al=a.length(),bl=b.length();i<al&&j<bl;){
			if(a[i]>b[j]){
				++j;
			}
			else if(a[i]==b[j]){
				ans+=a[i];
				++i;
				++j;
			}
			else{
				++i;
			}
		}
		cout << ans << "\n";
	}
}