ZOJ 1004 Anagrams by Stack（DFS+数据结构）

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 =0; i<ans.size(); i++)
        cout<<ans[i]<<" ";  //注意空格
    cout<<endl;
}

void dfs(int x,int y){
    if(x==len && y==len)
        print();
    if(x+1<=len){
        p.push(str1[x]);
        ans.push_back('i');
        dfs( x+1 , y);
        p.pop();
        ans.pop_back();
    }
    if(y+1<=x && y+1<=len &&p.top() == str2[y]){
        char temp = p.top();
        p.pop();
        ans.push_back('o');
        dfs(x,y+1);
        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(0,0);
        }
        cout<<"]"<<endl;
    }
    return 0;
}