UVa 732 Anagrams by Stack

题目描述给定两个单词源词SSS和目标词TTT。通过一个初始为空的栈可以对源词依次执行入栈i和出栈o操作每次入栈从源词当前未处理位置取一个字符压入栈顶出栈则将栈顶字符弹出并追加到输出序列。要求输出所有能使得最终输出序列恰好等于目标词TTT的合法操作序列按字典序io升序排列。每个测试用例输出以[和]包围序列内每个操作字符后跟一个空格序列间换行。若源词与目标词长度不同则直接输出空方括号对。输入格式输入包含多行每两行为一组数据。第一行为源词SSS第二行为目标词TTT。单词只包含小写字母长度不定。输入直至文件结束。输出格式对于每组数据首先输出一行[然后按字典序输出所有合法的操作序列每行一个序列序列中每个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 ]题目分析栈操作序列的长度固定为2×L2 \times L2×L其中LLL为源词长度因为每个字符恰好入栈一次并出栈一次。合法的序列必须满足任意前缀中o的数量不超过i的数量栈非空且最终i和o的数量均为LLL。我们需要筛选出那些能够将源词转换为目标词的操作序列。由于LLL不大单词长度通常不超过几十可枚举所有可能的操作序列但更好的方法是采用回溯法实时模拟栈和匹配过程避免生成大量无效序列。解题思路采用递归回溯backtracking\texttt{backtracking}backtracking模拟栈操作。定义全局数组stack\textit{stack}stack模拟栈当前栈顶索引为top\textit{top}top初始为000源词已处理位置src\textit{src}src从000开始目标词已匹配位置dst\textit{dst}dst从000开始以及当前操作序列数组seq\textit{seq}seq。递归过程如下步骤1\texttt{1}1. 若dstL\textit{dst} LdstL说明目标词已完全匹配此时当前操作序列即为一个合法解输出该序列并返回。步骤2\texttt{2}2. 若srcL\textit{src} LsrcL则可以选择将源词的下一个字符压入栈将S[src]S[\textit{src}]S[src]放入stack[top]\textit{stack}[\textit{top}]stack[top]top\textit{top}top增111记录操作i递归调用backtrack(src1,dst)\textit{backtrack}(\textit{src}1, \textit{dst})backtrack(src1,dst)回溯时恢复top\textit{top}top。步骤3\texttt{3}3. 若top0\textit{top} 0top0且stack[top−1]T[dst]\textit{stack}[\textit{top}-1] T[\textit{dst}]stack[top−1]T[dst]则可以选择弹出栈顶字符top\textit{top}top减111记录操作odst\textit{dst}dst增111递归调用回溯时恢复top\textit{top}top和栈顶字符以便后续其他分支使用。由于先尝试入栈操作后尝试出栈操作而字典序中i小于o因此输出序列自然按字典序升序排列。递归过程中所有分支均被探索保证了完整性。当源词与目标词长度不同时直接输出空方括号对无需搜索。代码实现// Anagrams by Stack// UVa ID: 732// Verdict: Accepted// Submission Date: 2017-02-17// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string from,to;stringletters(110,0),sequences(110,0);intletters_idx,sequences_idx;voidbacktrack(intsequences_idx,intsource,intdest){if(destto.length()){for(inti0;isequences_idx;i){if(i0)cout ;coutsequences[i];}cout\n;return;}if(sourcefrom.length()){letters[letters_idx]from[source];sequences[sequences_idx]i;backtrack(sequences_idx1,source1,dest);letters_idx--;}if(letters_idx0letters[letters_idx-1]to[dest]){sequences[sequences_idx]o;letters_idx--;backtrack(sequences_idx1,source,dest1);letters[letters_idx]to[dest];}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinfromto){if(from.length()!to.length()){cout[\n]\n;continue;}cout[\n;letters_idx0;backtrack(0,0,0);cout]\n;}return0;}总结本题通过回溯法枚举所有合法的入栈出栈操作序列并实时检查能否匹配目标词。关键在于先入栈后出栈的递归顺序保证了字典序输出且利用栈的模拟避免了生成无效序列。该解法时间复杂度为O(22L)O(2^{2L})O(22L)最坏情况但实际有效序列数量有限且单词长度通常较小能够高效运行。注意输出格式要求每个操作后跟空格序列末尾无多余空格以及空方括号对的处理。