C ++ / C / Java：Anagrams-从原始字符串到目标；

Question

我正在尝试解决此问题：http :
//uva.onlinejudge.org/external/7/732.html。对于给定的示例，他们给我们提供了原始单词，例如
TRIT 和目标“组合”字符串 TIRT 。

目标： 我们必须输出所有有效的序列“ i”和“ o”（分别为推式和弹出式），这些序列从源字符串产生目标字符串。

因此，我正在考虑计算“ i”和“ o”的所有排列，但是减少了这种情况：

1） 如果当前排列以“ o”开头，则停止检查，因为所有下一个排列都将从此pop命令开始，并且从空堆栈中弹出内容是无效命令。

2） 如果在检查过程中发现一个’o’命令，并且堆栈中没有任何内容，请跳过这种情况。

3） 如果找到“ i”命令，但输入字符串中没有任何内容，请跳过这种情况。

4） 如果找到一个’o’命令并且当前期望的字符不是刚刚弹出的字符，则跳过该情况，因为这将永远不会到达目标字符串。

5） 不要搜索输入字符串和目标字符串的长度是否不同。

但我认为无论如何我可能都会获得我的称号…

我知道这个理论：排列也许一直在回溯。我只是很难实现它。

有人可以和我分享一些代码或想法吗？

PS：当然，任何可能减少执行时间的建议都会受到欢迎。

Answer 1

此第一个迭代解决方案具有指导意义。这不是最有效的方法，因为它在String所有地方都可以使用，但这是一个很好的起点。

import java.util.*;

public class StackAnagram {

    static void anagram(String s1, String s2, String stack, String instr) {
        if (s2.isEmpty()) {
            if (s1.isEmpty() && stack.isEmpty()) {
                System.out.println(instr.trim());
            }
            return;
        }
        if (!s1.isEmpty()) {
            anagram(s1.substring(1), s2, s1.charAt(0) + stack, instr + "i ");
        }
        if (!stack.isEmpty() && stack.charAt(0) == s2.charAt(0)) {
            anagram(s1, s2.substring(1), stack.substring(1), instr + "o ");
        }
    }

    static void anagram(String s1, String s2) {
        System.out.println("[");
        anagram(s1, s2, "", "");
        System.out.println("]");
    }

    public static void main(String args[]) {
        anagram("madam", "adamm");
        anagram("bahama", "bahama");
        anagram("long", "short");
        anagram("eric", "rice");
        anagram("ericc", "rice");
    }
}