java - C++/C/Java : Anagrams - from original string to target;

Question

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

目标:我们必须输出“i”和“o”(分别为 push 和 pop)的所有有效序列，它们从源字符串生成目标字符串。

所以，我正在考虑计算 "i"和 "o"的所有排列，但削减这种情况:

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

2)如果在检查过程中发现“o”命令并且堆栈中没有任何内容，则跳过这种情况。

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

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

5) 如果输入字符串和目标字符串的长度不同，则不进行搜索。

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

我知道这个理论:也许排列和回溯。我只是在实现它时遇到了太多困难。

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

P.S.:当然，我们欢迎任何可能减少执行时间的建议。

Answer 1

这是一个有趣的问题，我相信下面的方法(找到所有使 *from* 字符串成为前序和 *to* 字符串成为中序的树，更多细节见下文)，如果正确实现会非常快:比蛮力递归要好得多，因为它很容易“知道”每一步可能出现的子问题。

事实上，我做了一个小实验，并将其与给出的一个强力答案进行了比较。 (注意:C# 代码位于线程底部)。 preorder/inorder 的算法不是最优的，实际上可以改进。当然，蛮力算法的优点是简洁，并且对于较小规模的问题可能足够好(并且性能更好)。

结果如下。特别是查看较长字符串的最后两个结果，其中预序/中序方法比蛮力快得多。解决的子问题数量之间存在很大差异这一事实应该让您相信这不仅仅是由于数据，而是随着字符串变长(可能有更多重复的字符)，蛮力解决方案本质上必须处理更多不必要的子问题。使用蛮力解决方案进行任何记忆化是可能的，但似乎非常困难。

------------------------
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
      /    \
     a      m
    / \    / \
   .   d  .   .
      / \  
     .   a 
        / \
       .   .

在哪里。是空节点。

考虑一个预订单，其中您还输出空节点(一个点 = '.')。

这为我们提供了预购:m a 。 d. A 。 .米。 .

考虑中序，没有空节点，它是:a d a m m

现在考虑以下问题:

您接受预订:m a。 d. a .. m .. 每次你看到一个非空(或非点)，你插入一个堆栈。每次你看到一个空值(或点)，你就会弹出堆栈的顶部。您可以忽略最后一个 .，因为它会导致弹出空堆栈。

我们可以手动运行它:

m a . d . a . . m ..    | Stack =                    | Output = 

Push m 

  a . d . a . . m ..    | Stack = m                  | Output = 

Push a 

  . d . a . . m ..      | Stack = a m                | Output = 

Pop 

    d . a . . m ..      | Stack =  m                 | Output = a

Push d

      . a . . m ..      | Stack =  d m               | Output = a

Pop 
        a . . m ..      | Stack =    m               | Output = a d

Push a
          . . m ..      | Stack =   a m              | Output = a d

Pop, Pop (sorry getting a little lazy)

              m ..      | Stack =                    | Output = a d a m 

Push m, Pop
                 .      | Stack =                    | Output = a d a m m.

现在将其输出与顺序进行比较。这是相同!

事实上，这对于一般的二叉树是正确的，可以使用归纳法证明，这是树的一个很好的属性，我们可以利用它来解决这个问题。

证明的简要概述:观察空节点数 = 1 + 非空节点数。这意味着当您完成弹出左树时，由于左树的最后一个空值，您将弹出根，因此所有这些推送和弹出转换为(左)根(右)。

因此给定一个字符串 A(如 madam)，您需要仅使用 push 和 pops 将其转换为字符串 B(如 adamm)，我们有以下解决问题的方法:

找到所有前序为 A 中序为 B 的树

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

在给定前序/中序的情况下找到一棵树是一个标准问题，并且有许多快速解决方案。对于这个问题，您可能只需要稍微调整其中一个解决方案。

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

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

我猜您确实想编写自己的 C/C++/Java 代码，所以我将提供我拥有的 C# 原型(prototype)代码。

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<string, Dictionary<string, List<string>>> memoized = 
                     new Dictionary<string, Dictionary<string, List<string>>>();

        public static List<string> Instructions(string from, string to)
        {
            count = 0;
            if (from.Length != to.Length)
            {
                return new List<string>();
            }

            List<string> 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<char, int> d = new Dictionary<char, int>();

            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<string> Instructions(string from, 
                  int startF, int endF, string to, int startTo, int endTo)
        {

            List<string> inst;

            // Null tree.
            if (startF >= endF || startTo >= endTo)
            {
                inst = new List<string>();
                inst.Add("o ");
                count++;
                return inst;
            }

            string subFrom = from.Substring(startF, endF - startF);
            string subTo = to.Substring(startTo, endTo - startTo);
            Dictionary<string, List<string>> dict;
            if (memoized.TryGetValue(subFrom, out dict))
            {
                if (dict.TryGetValue(subTo, out inst))
                {
                    return inst;
                }
            }
            else
            {
                memoized[subFrom] = new Dictionary<string, List<string>>();
            }

            count++;
            inst = new List<string>();

            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<string> leftInst = Instructions(from, startF + 1, 
                                       startF + j + 1, to, startTo, startTo + j);

                    List<string> 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<string> 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<string> anagram(String s1, String s2)
        {
            count = 0;
            if (s1.Length != s2.Length)
            {
                return new List<string>();
            }

            List<string> l = new List<string>();
            anagram(s1, s2, "", "", l);
            return l;
        }
    }
}

程序.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<string> 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<string> 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);
        }
    }
}