This is an interesting problem, and I believe the approach below (find all trees which make the *from* string their preorder and the *to* string their inorder, more details below), if implemented properly will be very fast: much better than brute force recursion, as it just 'knows' easily what the possible sub-problems are at each step.
In fact, I did a little experiment and compared it with one of the brute force answers given. (Note: C# code is at the bottom of the thread). The algorithm for preorder/inorder is not optimal and can actually be bettered. Of course, the brute force algorithm has the advantage of being concise and might well be good enough (and better performing) for smaller sized problems.
Below are the results. Especially look at the last two results for longer strings for which the preorder/inorder approach is much faster than brute force. The fact that there is a large difference between the number of sub-problems tackled should convince you that it is not solely due to data, but as the strings get longer (with possibly more repeated characters) the brute force solution inherently has to deal with a lot more unnecessary sub-problems. Doing any memoization with the brute force solution might be possible, but seems very difficult.
------------------------
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
For shorter strings, brute force wins out as there is lesser overhead, but the speed of the other algorithm really shows when the string gets longer. In any case, for shorter strings you can use brute force and switch to the preorder/inorder approach for longer ones to get the best of both worlds.
Now, a writeup regarding the method suggested:
Consider the following tree:
m
/ \
a m
/ \ / \
. d . .
/ \
. a
/ \
. .
where the . are null nodes.
Consider a preorder, in which you also output the null node (a dot = '.' ).
This gives us the pre-order to be: m a . d . a . . m . .
Consider the in-order, without the null nodes, it is: a d a m m
Now consider the following:
You take the preorder : m a . d . a .. m .. and each time you see a non null (or non-dot), you push onto a stack. Each time you see a null (or dot) you pop the top of the stack. You can ignore the last ., as that results in the pop of empty stack.
We can manually run through it:
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.
Now compare the output of this with the in-order. It is the same!
In fact, that this is true for general binary trees can be proved using induction and is a nice property of trees which we can exploit for this problem.
A brief sketch of the proof: Observe that number of null nodes = 1 + number of non-null nodes. This implies that when you are done popping the left tree, you pop the root because of the last null of the left tree and thus all this pushing and popping translates to (left) root (right).
Thus given a string A (like madam) which you need to transform to string B (like adamm) using only pushes and pops, we have the following approach to the problem:
Find all trees which have A as the preorder and B as the inorder
A preorder of that tree, outputting push for non-null and pop for null nodes (ignoring the last push) should give the required sequence.
Finding a tree given preorder/inorder is a standard problem and has many fast solutions. For this problem you probably just need to tweak one of those solutions a little.
Also, some of the advantages of this approach are
- Easily knowing which subproblem to tackle.
- Above point helps implement memoization (see code below).
- This algorithm can also be parallelized easily.
I am guessing you do want to write your own C/C++/Java code, so I will provide the C# prototype code I have.
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);
}
}
}