# 題目: 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/