d829 - 00146 - ID Codes

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一個由小寫字母組成的字串，並輸出該字串的下一個字母順序排列。如果輸入字串已經是字母順序的最大排列，則輸出 "No Successor"。輸入以 "#" 結尾。

解題思路

這題的核心在於找到給定字串的下一個字母順序排列。可以使用 std::next_permutation 函數來實現。next_permutation 函數會嘗試生成輸入序列的下一個字母順序排列，如果存在，則返回 true，否則返回 false。如果 next_permutation 返回 false，表示輸入字串已經是字母順序的最大排列，則輸出 "No Successor"。

複雜度分析

• 時間複雜度: O(N log N)，其中 N 是字串的長度。next_permutation 的最壞情況時間複雜度為 O(N)，而迴圈最多執行一次，因此整體時間複雜度為 O(N log N)。
• 空間複雜度: O(1)，因為我們只使用了常數額外的空間。

程式碼

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
	string a;
 	while(cin >> a){
 		if(a=="#")break;
 		bool k=0;
 		while(next_permutation(a.begin(),a.end())){  
        	cout << a << "\n";
			k=1; 
			break; 
   		} 
   		if(k==0)
   			cout << "No Successor\n";
	}
 }