e685 - 00732 - Anagrams by Stack
題目描述
題目要求找出所有將原始字串轉換為目標字串的堆疊操作序列，其中 "i" 代表 push，"o" 代表 pop。輸出結果需要按照字典順序排列。
解題思路
這題使用深度優先搜尋 (DFS) 搭配堆疊來解決。dfs 函式遞迴地探索所有可能的 push 和 pop 操作序列。
ans記錄目前 pop 出來的字串。sl記錄目前ans的長度。i記錄目前已 push 的原始字串的索引。o記錄目前已 pop 的字串的索引。stk記錄目前的堆疊狀態。now記錄目前的 push/pop 操作序列。
在 dfs 函式中，如果 ans 的長度不為 0 且 ans 的最後一個字元不等於 goal 的對應位置的字元，則回傳。如果 ans 的長度等於 goal 的長度，則輸出 now。
如果 i 小於原始字串的長度，則將 a[i] push 到堆疊中，並遞迴呼叫 dfs。
如果 o 小於原始字串的長度且堆疊不為空，則將堆疊頂端的字元 pop 出來，並遞迴呼叫 dfs。
複雜度分析
- 時間複雜度: O(2^n * n)，其中 n 是字串的長度。最壞情況下，需要探索所有可能的 push 和 pop 操作序列，每個操作序列的長度為 2n。
- 空間複雜度: O(n)，主要來自堆疊
stk和遞迴呼叫堆疊。
程式碼
#include <iostream>
#include <stack>
using namespace std;
int al,nl,gl;
string a,goal;
inline void dfs(string ans,int sl,int i,int o,stack <char> stk,string now){
if(sl&&ans[sl-1]!=goal[sl-1])return;
else if(sl==gl){
now[nl]='\n';
cout << now;
return;
}
if(i<al){
stk.push(a[i]);
dfs(ans,sl,i+1,o,stk,now+"i ");
stk.pop();
}
if(o<al&&!stk.empty()){
ans+=stk.top();
stk.pop();
dfs(ans,sl+1,i,o+1,stk,now+"o ");
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(getline(cin,a)){
getline(cin,goal);
al=a.length();
gl=goal.length();
nl=(al<<2)-1;
stack <char> stk;
cout << "[\n";
if(al==gl)dfs("",0,0,0,stk,"");
cout << "]\n";
}
}