C ++ / C / Java：Anagrams – 从原始字符串到目标;

我正试图解决这个问题： http ： //uva.onlinejudge.org/external/7/732.html 。 对于给定的示例，它们给我们原始单词，例如TRIT和目标“anagramed”字符串TIRT 。

目标：我们必须输出所有有效的’i’和’o’序列（分别是push和pop），它们从源字符串中产生目标字符串。

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

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

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

3）如果找到’i’命令并且输入字符串中没有任何内容，则跳过该情况。

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

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

但我认为无论如何它可能会让我TLE ……

我知道这个理论：也许是一种排列，一直是回溯。 我实施它有太多困难。

有谁能请与我分享一些代码或想法吗？

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"); } } 

Answer 2

这是一个有趣的问题，我相信下面的方法（如果正确实施， find all trees which make the *from* string their preorder and the *to* string their inorder ，下面有更多详细信息的find all trees which make the *from* string their preorder and the *to* string their inorder ）将非常快：比蛮力递归，因为它只是“容易”知道每一步可能存在的子问题。

事实上，我做了一个小实验，并将其与给出的蛮力答案之一进行了比较。 （注意：C＃代码位于线程的底部）。 预订/订购的算法不是最佳的，实际上可以更好。 当然，powershell算法具有简洁的优点，并且对于较小尺寸的问题可能足够好（并且表现更好）。

以下是结果。 特别是对于较长字符串的最后两个结果，其中预订/顺序方法比蛮力快得多。 处理的子问题数量之间存在很大差异这一事实应该说服您，这不仅仅是由于数据，而是随着字符串变得更长（可能更多重复字符），powershell解决方案本身就必须处理更多不必要的子问题。 使用暴力解决方案进行任何记忆都是可能的，但似乎非常困难。

 ------------------------ bahama(Length:6) bahama(Length:6) PreorderInorder TimeTaken: 00:00:00.0230000 Number of recursive calls: 20 Number of results returned: 4 Brute Force TimeTaken: 00:00:00.0030000 Number of recursive calls: 47 Number of results returned: 4 ------------------------ madameric(Length:9) adammcire(Length:9) PreorderInorder TimeTaken: 00:00:00 Number of recursive calls: 28 Number of results returned: 4 Brute Force TimeTaken: 00:00:00 Number of recursive calls: 107 Number of results returned: 4 ------------------------ trittrottotr(Length:12) tirttorttort(Length:12) PreorderInorder TimeTaken: 00:00:00.0010000 Number of recursive calls: 103 Number of results returned: 63 Brute Force TimeTaken: 00:00:00.0010000 Number of recursive calls: 1301 Number of results returned: 63 ------------------------ bahamabhahambahamamadambahamabhahambahama(Length:41) bahamabhahambahamamadambahamabhahammahaba(Length:41) PreorderInorder TimeTaken: 00:00:01.1710000 Number of recursive calls: 2059 Number of results returned: 97472 Brute Force TimeTaken: 00:00:18.2610000 Number of recursive calls: 41784875 Number of results returned: 97472 ------------------------ bahamabhahambahamamadambahamabhahambahama(Length:41) bahamabhahambahamamadambahamabhahambahama(Length:41) PreorderInorder TimeTaken: 00:00:00.1790000 Number of recursive calls: 315 Number of results returned: 20736 Brute Force TimeTaken: 00:00:17.1680000 Number of recursive calls: 41062923 Number of results returned: 20736 

对于较短的字符串，蛮力因为开销较小而获胜，但其他算法的速度确实显示字符串变长时。 在任何情况下，对于较短的琴弦，您可以使用蛮力并切换到预订/订购方法以获得更长的琴弦，以获得两全其美的效果。

---

现在，关于该方法的一篇文章建议：

考虑以下树：

  m / \ am / \ / \ . d . . / \ . a / \ . . 

在哪里。 是空节点。

考虑一个预订单，您还可以输出空节点（点=’。’）。

这给了我们预订： ma . d . a . . m . . ma . d . a . . m . .

考虑有序，没有空节点，它是： adamm

现在考虑以下内容：

你接受预购： ma . d . a .. m .. ma . d . a .. m .. ma . d . a .. m ..每次看到非空（或非点）时，都会推入堆栈。 每次看到null（或点）时，都会弹出堆栈顶部。 您可以忽略最后一个。，因为这会导致弹出空堆栈。

我们可以手动运行它：

 ma . d . a . . m .. | Stack = | Output = Push ma . d . a . . m .. | Stack = m | Output = Push a . d . a . . m .. | Stack = am | Output = Pop d . a . . m .. | Stack = m | Output = a Push d . a . . m .. | Stack = dm | Output = a Pop a . . m .. | Stack = m | Output = ad Push a . . m .. | Stack = am | Output = ad Pop, Pop (sorry getting a little lazy) m .. | Stack = | Output = adam Push m, Pop . | Stack = | Output = adam m. 

现在将其输出与有序进行比较。 它是一样的 ！

实际上，对于一般二叉树来说，这是正确的，可以使用归纳certificate，并且是我们可以利用这个问题的树的一个很好的属性。

certificate的简要草图：观察空节点数= 1 +非空节点数。 这意味着当您完成弹出左侧树时，由于左侧树的最后一个空值而弹出根，因此所有这些推送和弹出都转换为（左）根（右）。

因此，给定一个字符串A（像女士一样），你只需要使用推送和弹出来转换为字符串B（如adamm），我们有以下方法解决问题：

Find all trees which have A as the preorder and B as the inorder

该树的预订，输出非空的推送和空节点的弹出（忽略最后一次推送）应该给出所需的序列。

找到预先订购/订购的树是一个标准问题，并有许多快速解决方案。 对于这个问题，您可能只需稍微调整其中一个解决方案。

此外，这种方法的一些优点是

• 轻松了解要解决的子问题。
• 以上几点有助于实现记忆（见下面的代码）。
• 该算法也可以很容易地并行化。

我猜你确实想编写自己的C / C ++ / Java代码，所以我将提供我所拥有的C＃原型代码。

StackAnagram.cs：

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SO { public class StackAnagram { public static int count = 0; static Dictionary>> memoized = new Dictionary>>(); public static List Instructions(string from, string to) { count = 0; if (from.Length != to.Length) { return new List(); } List l = Instructions(from, 0, from.Length, to, 0, to.Length); return l; } private static bool IsAnagram(string from, string to, int startF, int endF, int startTo, int endTo) { Dictionary d = new Dictionary(); for (int i = startF; i < endF; i++) { if (d.ContainsKey(from[i])) { d[from[i]]++; } else { d[from[i]] = 1; } } for (int i = startTo; i < endTo; i++) { if (d.ContainsKey(to[i])) { d[to[i]]--; if (d[to[i]] == 0) { d.Remove(to[i]); } } else { return false; } } if (d.Count > 0) { return false; } return true; } private static List Instructions(string from, int startF, int endF, string to, int startTo, int endTo) { List inst; // Null tree. if (startF >= endF || startTo >= endTo) { inst = new List(); inst.Add("o "); count++; return inst; } string subFrom = from.Substring(startF, endF - startF); string subTo = to.Substring(startTo, endTo - startTo); Dictionary> dict; if (memoized.TryGetValue(subFrom, out dict)) { if (dict.TryGetValue(subTo, out inst)) { return inst; } } else { memoized[subFrom] = new Dictionary>(); } count++; inst = new List(); if (!IsAnagram(from, to, startF, endF, startTo, endTo)) { goto ret; } for (int j = 0; j < endTo - startTo; j++) { // Found possible root if (from[startF] == to[startTo + j]) { List leftInst = Instructions(from, startF + 1, startF + j + 1, to, startTo, startTo + j); List rightInst = Instructions(from, startF + j + 1, endF, to, startTo + j + 1, endTo); if (rightInst.Count <= 0) { continue; } foreach (string l in leftInst) { foreach (string r in rightInst) { inst.Add("i " + l + r); } } } } ret: memoized[subFrom][subTo] = inst; return inst; } } public class StackAnagramBrute { public static int count = 0; static void anagram(String s1, String s2, String stack, String instr, List insts) { count++; if (s2.Length == 0) { if (s1.Length == 0 && stack.Length == 0) { insts.Add(instr.Trim()); } return; } if (!(s1.Length == 0)) { anagram(s1.Substring(1), s2, s1[0] + stack, instr + "i ", insts); } if (!(stack.Length == 0) && stack[0] == s2[0]) { anagram(s1, s2.Substring(1), stack.Substring(1), instr + "o ", insts); } } public static List anagram(String s1, String s2) { count = 0; if (s1.Length != s2.Length) { return new List(); } List l = new List(); anagram(s1, s2, "", "", l); return l; } } } 

Program.cs中

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Text.RegularExpressions; namespace SO { class Program { static void Main(string[] args) { string[] from = { "bahama", "madameric", "trittrottotr", "bahamabhahambahamamadambahamabhahambahama", "bahamabhahambahamamadambahamabhahambahama" }; string[] to = { "bahama", "adammcire", "tirttorttort", "bahamabhahambahamamadambahamabhahammahaba", "bahamabhahambahamamadambahamabhahambahama" }; for (int i = 0; i < from.Length; i++) { CompareAlgorithms(from[i], to[i]); } } static void CompareAlgorithms(string from, string to) { Console.WriteLine("------------------------"); Console.WriteLine(from + "(Length:" + from.Length + ")"); Console.WriteLine(to + "(Length:" + to.Length + ")"); DateTime start = DateTime.Now; List inst = StackAnagram.Instructions(from, to); DateTime end = DateTime.Now; TimeSpan t = end - start; Display("PreorderInorder", t, StackAnagram.count, inst.Count); DateTime startBrute = DateTime.Now; List instBrute = StackAnagramBrute.anagram(from, to); DateTime endBrute = DateTime.Now; TimeSpan tBrute = endBrute - startBrute; Display("Brute Force", tBrute, StackAnagramBrute.count, instBrute.Count); } static void Display(string method, TimeSpan t, int callCount, int resultCount) { Console.WriteLine(method); Console.Write("\t"); Console.Write("TimeTaken: "); Console.WriteLine(t.ToString()); Console.Write("\t"); Console.Write("Number of recursive calls: "); Console.WriteLine(callCount); Console.Write("\t"); Console.Write("Number of results returned: "); Console.WriteLine(resultCount); } } }