# 題目: UVa 732 - Anagrams by Stack

# 題目說明

給你兩個字串及一個stack，找出所有能使前者變成後者的所有input、output組合

---

INPUT:
每筆資料輸入兩個字串，起始字串及目標字串

---

OUTPUT:
輸出起始字串能透過stack轉變為目標字串的所有組合

# 解題方法

使用dfs，每次將字串push及pop，最後如果符合目標字串則輸出

# 參考程式碼

#include <iostream>
#include <stack>

using namespace std;

string in, target;

void dfs(stack<char> starts, string results, stack<char> stacks, string out, int n)
{
    if (n == in.size() * 2) {
        if (results == target) cout << out << "\n";
        return;
    }

    if (starts.size() > 0) {
        auto tmp1 = stacks, tmp2 = starts;
        tmp1.emplace(tmp2.top());
        tmp2.pop();
        dfs(tmp2, results, tmp1, out + (n ? " i" : "i"), n + 1);
    }

    if (stacks.size() > 0 && stacks.top() == target[results.size()]) {
        auto tmp1 = stacks;
        tmp1.pop();
        dfs(starts, results + stacks.top(), tmp1, out + " o", n + 1);
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	while (cin >> in >> target) {

        stack<char> starts, stacks;
        for (int i = in.size() - 1; i >= 0; --i) starts.emplace(in[i]);

		cout << "[\n";
        if (in.size() == target.size()) dfs(starts, "", stacks, "", 0);
		cout << "]\n";
	}

	return 0;
}

# 程式碼(修正版)

#include <iostream>
#include <string>
#include <stack>

using namespace std;
typedef tuple<int, int, int> tp;

string s, t;
stack<char> st;

void dfs(int i1, int i2, string ret)
{
	if (i2 == t.size())
	{
		cout << ret << "\n";
		return;
	}

	if (i1 < s.size())
	{
		st.emplace(s[i1]);
		dfs(i1 + 1, i2, ret + (ret.empty() ? "i" : " i"));
		st.pop();
	}

	if (!st.empty() && st.top() == t[i2])
	{
		auto tmp = st.top();
		st.pop();
		dfs(i1, i2 + 1, ret + " o");
		st.emplace(tmp);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	while (cin >> s >> t)
	{
		st = stack<char>();
		cout << "[\n";
		if (s.size() == t.size()) dfs(0, 0, "");
		cout << "]\n";
	}
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%20732/