Это интересная проблема, и я полагаю, что приведенный ниже подход (find all trees which make the *from* string their preorder and the *to* string their inorder, подробности ниже), если он будет реализован должным образом, будет очень быстрым: гораздо лучше, чем рекурсия методом грубой силы, поскольку он просто «знает», что возможно подзадачи находятся на каждом этапе.
На самом деле я провел небольшой эксперимент и сравнил его с одним из приведенных ответов о грубой силе. (Примечание: код C # находится в нижней части потока). Алгоритм предварительного заказа / заказа не является оптимальным и может быть улучшен. Разумеется, алгоритм грубой силы имеет преимущество в том, что он лаконичен и вполне может быть достаточно хорошим (и более эффективным) для задач меньшего размера.
Ниже приведены результаты. Особенно обратите внимание на последние два результата для более длинных струн, для которых подход «предзаказ / порядок» намного быстрее, чем «грубая сила». Тот факт, что существует большое различие между количеством решаемых подзадач, должен убедить вас, что это происходит не только из-за данных, но поскольку строки становятся длиннее (возможно, с более повторяющимися символами), решение грубой силы по сути должно иметь дело с намного больше ненужных подзадач. Возможно, можно сделать какие-либо заметки с помощью метода грубой силы, но это кажется очень трудным.
------------------------
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 . . m . .
Рассмотрим порядок без нулевых узлов: 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 (например, мадам), которую нужно преобразовать в строку B (например, adamm), используя только нажатия и нажатия, мы имеем следующий подход к проблеме:
Find all trees which have A as the preorder and B as the inorder
Предзаказ этого дерева, выводящий push для ненулевых и pop для нулевых узлов (игнорируя последний push) должен дать требуемую последовательность.
Поиск дерева с заданным предзаказом / порядком является стандартной проблемой и имеет много быстрых решений. Для этой проблемы вам, вероятно, просто нужно немного подправить одно из этих решений.
Кроме того, некоторые из преимуществ этого подхода
- Легко зная, какую подзадачу решить.
- Вышеуказанный пункт помогает реализовать запоминание (см. Код ниже).
- Этот алгоритм также можно легко распараллелить.
Я предполагаю, что вы действительно хотите написать свой собственный код на 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<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;
}
}
}
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<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);
}
}
}