1004. Anagrams by Stack作者:ZOJ 出题组;单位:zoj;How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convertTROTtoTORT:[i i i i o o o oi o i i o o i o]where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.Input Specification:The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word. The end of input is marked by end of file.Output Specification:For each input pair, your program should produce a sorted list of valid sequences ofiandowhich produce the target word from the source word. Each list should be delimited by[]and the sequences should be printed in dictionary order. Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line.ProcessA stack is a data storage and retrieval structure permitting two operations:Push - to insert an item andPop - to retrieve the most recently pushed itemWe will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the wordFOOis input, then the sequence:SequenceExplanationi i o i o ois valid, buti i ois not (its too short), neither isi i o o o i(theres an illegal pop of an empty stack)Valid sequences yield rearrangements of the letters in an input word. For example, the input wordFOOand the sequence i i o i o o produce the anagramOOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.Sample Input:madamadammbahamabahamalongshortericriceSample Output:[i i i i o o o i o oi i i i o o o o i oi i o i o i o i o oi i o i o i o o i o][i o i i i o o i i o o oi o i i i o o o i o i oi o i o i o i i i o o oi o i o i o i o i o i o][][i i o i o i o o]代码长度限制32 KB时间限制2000 ms内存限制64 MB栈限制8192 KB题意通过栈完成回文字符串给定两个单词 word1 和 word2假设有一个字符栈stack通过对字符的栈操作i 为 push 入栈操作o 为 pop 出栈操作可能把 word1 转变为 word2那么这一系列的栈操作由字母 i 和 o 组成就是一个可行的操作。题目要求输出所有可以完成把 w1 转变为 w2 的操作并按照字典顺序输出它们。例如把 TROT 转变为 TORT则以下两种操作序列都可以做到[i i i i o o o oi o i i o o i o]分析这是一个困扰了我很多年的问题从我最开始做 ZOJ 题目开始就遇到这个问题虽然这个题目看起来好像非常的简单但我常年来一直没想到一个比较好的解题办法所以这道题一直搁置但是它一直在我的心理。表面上看这道题有子问题很类似动态规划类题目但是因为它每个子问题都有多组解所以常规的解决动态规划问题使用的二维矩阵那种存储解的方法又并不合适。用穷举法显然也不合适。所以我想来想去还是没想好这个题目的做法。直到昨天我决定去做一下这道题。题意里讲到的栈操作本身是非常直观的大家都知道栈具有 FILO 先进后出的特点所以我们把一个字符 push 到栈中以后可以稍后再 pop 出这就实现了把一个字符“稍晚”再输出的效果也就是相当于能把一个字符和它后面的多个字符颠倒它们之间的顺序假设我们不 care 后面的多个字符之间的排列。比如说假如有一个字符 a 位于单词 word1 的第一个字符转换后我们让 a 位于单词 word2 的最后一个字符word1:a[xxxx...]word2:[xxxx...]a对于这样两个单词可以用 i [......] o 这样的操作[......] 是对后面多个字符的合法栈操作序列并能将这些字符全部输出达到让 a 出现在它后面 n 个字符的后面的输出结果。当然[xxxx...] 这多个字符之间可能会顺序比较混乱目前我们不在意这一点。这样我们就可以令 a 和它后面的多个字符颠倒顺序让 a 出现在输出单词的最后面。不难得出结论有且仅有 i [ ... ] o 这一种操作可以让长度为 len 的 word1 的首个字符出现在 word2 的结尾位置。其中[ ... ] 是对 (len - 1) 个字符的任一合法栈操作序列。对 n 个字符的合法栈操作序列是指对连续的 n 个字符中的每个字符都入栈和出栈过一次且所有操作合法操作后 stack 栈顶指针的指向位置和执行该操作序列之前相同。也就是说该操作序列会把 n 个字符进行重新排列并产生一个新的 n 个字符的输出结果。这一点很重要有了这个基本结论就可以开始把原问题拆解为规模更小的子问题。我们在 word2 中逐个字符检查看它是不是 word1 的首个字符如果在 word2 的某个位置的字符是 word1 的首个字符那么问题将会分解为如下因此解决该问题的方法是从 word2 的第一个字符开始遍历 word2 的每个字符如果 word2 的 i-th (0-based) 字符和 word1 的首字符假设为 a相同那么在索引为 i 的位置就可以把原问题分解为两个子问题word1 中位于 a 后面的 i 个字符如何通过合法栈操作转变为 word2 中的前 i 个字符。word1 中尾部的 (len - i - 1) 个字符如何通过合法栈操作转变为 word2 中的尾部的 len - i - 1) 个字符。如果有了以上的子问题的解就可以得出当前问题的一组解把 a 入栈加上子问题1的解把 a 出栈加上子问题2的解就是当前问题的解。如果把子问题1的解集 (注意包含多个解)称为 child1把子问题2的解集 (注意包含多个解)称为 child2那么当前问题的解将会增加 child1.size() * child2.size() 个。可以把新增加的这些解表示为{i Child1 o} × {Child2}当然前提是子问题1和2必须都有解。可以看出子问题1和2和当前问题属于本质相同的问题这启发我们可以使用递归函数来解决这个问题。首先定义解决问题的递归函数的原型如下typedef struct tagSTR { char x[256]; } STR, *PSTR; //把 word1 通过栈操作转换为 word2所有可能的操作序列被存储在 results 中。 //[in] const char* word1: 第一个单词。 //[in] const char* word2: 第二个单词长度和 word1 相同。 //[in] int len: word1 和 word2 包含的字符数量 (strlen)。 //[out] std::vectorSTR results: 存储从 word1 转换到 word2 的所有栈操作序列。 //返回值: bool 是否有解。返回值 !results.empty(); bool Convert(const char* word1, const char* word2, int len, std::vectorSTR results);然后定义规模最小问题的解回归条件为了求解代码的一致性和简洁性对问题边界做以下定义当 len 0 时有一个解长度为 0 的空字符串注非 NULL 值。当 len 1 时如果两个单词的首字符相同则有一个解io否则问题无解。在函数返回时通过判断 results.empty() 的值也可以判断问题是否有解results 为空集合则无解。如果任何一个子问题无解则在当前索引 i 的位置无解继续检查 word2 的下一个字符。当找到所有解后再对包含所有解的容器做一次按升序排序即可。用于提交的代码solution code