ZOJ 1004 Anagrams by Stack(DFS+数据结构)

时间:2024-06-26 14:05:32

Anagrams by Stack

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4

题目大意:输入两个字符串序列,判断能否通过对第一个字符串进行进栈出栈操作得到第二个字符串,若能则输出所有能达到的进出栈操作过程。我通过全排列每得到一组操作过程,则用函数按照这个操作过程,判断能否得到第二个字符串,若能则表明此操作过程可行,输出。

代码如下:

 # include<iostream>
# include<stack>
# include<vector>
# include<algorithm>
using namespace std; string str1,str2;
stack<char> p;
vector<char> ans;
int len; void print(){
for(int i =; i<ans.size(); i++)
cout<<ans[i]<<" "; //注意空格
cout<<endl;
} void dfs(int x,int y){
if(x==len && y==len)
print();
if(x+<=len){
p.push(str1[x]);
ans.push_back('i');
dfs( x+ , y);
p.pop();
ans.pop_back();
}
if(y+<=x && y+<=len &&p.top() == str2[y]){
char temp = p.top();
p.pop();
ans.push_back('o');
dfs(x,y+);
p.push(temp);
ans.pop_back();
}
} int main(){
while(cin >> str1 >> str2){
len =str1.length();
string t1 = str1, t2 = str2;
sort(t1.begin(),t1.end());
sort(t2.begin(),t2.end());
cout<<"["<<endl;
if(t1 == t2){
dfs(,);
}
cout<<"]"<<endl;
}
return ;
}