题解：UVA732 Anagrams by Stack

xyx4042025-07-042025-07-04

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

题意简述：

多组数据。
每组数据给出两个字符串（源字符串和目标字符串），输出所有通过栈操作将源单词转为目标单词的操作字符串（i 表示入栈，o 表示出栈）。
操作字符串按字典序输出。

思路：

使用 DFS 算法，暴力模拟出栈入栈操作，为了保证按字典序从小到大输出，应该优先模拟入栈操作。因为入栈用字母 i 表示，出栈用字母 o 表示，很明显 i 的字典序比 o 小。

特别注意：本题不允许行末多余空格。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
string st,en;
stack<char>sta;
int lenen;
void dfs(int s,int e,string op/*操作*/){
	if(e==lenen){
		cout<<op<<"\n";
		return;
	}
//	cout<<op<<"\n";
	// i 的 ASCII 码值小于 o 为了保证字典序从小到大，先从小的开始
	if(s<st.size()){// 模拟入栈
		sta.push(st[s]);
		dfs(s+1,e,op+"i ");
		sta.pop();// 回溯
	}
	if(!sta.empty()&&sta.top()==en[e]){
		char k=sta.top();
		sta.pop();
		if(e+1!=lenen)dfs(s,e+1,op+"o ");// 不要问为什么这么写
		else dfs(s,e+1,op+"o");// 因为直接 dfs(s,e+1,op+"o ") 会 PE
		sta.push(k);
	}
	
	return;
}
int main(){
	while(cin>>st>>en){
		cout<<"[\n";
		string a=st,b=en;
		lenen=en.size();
		sort(a.begin(),a.end());
		sort(b.begin(),b.end());
		if(a==b)dfs(0,0,"");// 特判类似于样例中的 st=long,en=short 两个字符串字符不一样的情况 
		cout<<"]\n";
	}
	return 0;
}