题解：UVA732 Anagrams by Stack

xyx404 · 2025-07-04 12:03:03 · 题解

题意简述：

多组数据。
每组数据给出两个字符串（源字符串和目标字符串），输出所有通过栈操作将源单词转为目标单词的操作字符串（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;
}