526互联

NOJ[1143] 字母转换

发布时间 2023-09-28 09:33:07作者: hello_33

描述：

通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:
[
i i i i o o o o
i o i i o o i o
]

输入：

给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。

输出：

所有的进栈和出栈序列,输出结果需满足字典序

输入样例：

madam
adamm
bahama
bahama
long
short
eric
rice

输出样例：

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

题解：

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

char str1[20], str2[20];
stack <char> a;
char ans[40];
int len1, len2;
void dfs(int t, int num1, int num2);
void output();

int main()
{
	while (cin >> str1 >> str2)
	{
		len1 = strlen(str1);
		len2 = strlen(str2);
		cout << "[" << endl;
		if (len1 == len2)
		{
			dfs(0, 0, 0);
		}
		cout << "]" << endl;
	}
}

void dfs(int t, int num1, int num2)
{
	if (t == 2 * len1)
	{
		output();
		return;
	}
	if (num1 < len1)
	{
		ans[t] = 'i';
		a.push(str1[num1]);
		dfs(t + 1, num1 + 1, num2);
		a.pop();
	}
	if (!a.empty() && a.top() == str2[num2])
	{
		ans[t] = 'o';
		char temp = a.top();
		a.pop();
		dfs(t + 1, num1, num2 + 1);
		a.push(temp);
	}
}

void output()
{
	for (int i = 0; i < 2 * len1 - 1; i++)
	{
		cout << ans[i] << " ";
	}
	cout << ans[2 * len1 - 1] << endl;
}