題目： UVa - 732 - Anagrams by Stack

題目說明

給兩個字串，str、target，求 str 透過 Stack 的 push() 及 pop() 後能否轉換成 target，若可以則輸出所有能達成的操作順序。

解題思路

使用 DFS 即可，對於每層 DFS，可以 push() 進 Stack 也可以 pop() 出 Stack，先直接 push() 並往下執行，接著判斷，若 Stack 的 top() 等於當前檢查到的字元則 pop() 並往下執行。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <string>
#include <stack>
#include <functional>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    string str, target;
    stack<char> s;

    function<void(int, int, string)> dfs = [&](int i1, int i2, string ret)
    {
        if (i2 == target.length()) { cout << ret << '\n'; return; }

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

        if (!s.empty() && s.top() == target[i2])
        {
            auto tmp = s.top();
            s.pop();
            dfs(i1, i2 + 1, ret + (ret.empty() ? "o" : " o"));
            s.push(tmp);
        }
    };

    while (cin >> str >> target)
    {
        s = stack<char>();
        cout << "[\n";
        if (str.length() == target.length() && !str.empty()) dfs(0, 0, "");
        cout << "]\n";
    }
}