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

I'm trying to solve this problem : http://uva.onlinejudge.org/external/7/732.html. For the given example, they give us the original word, for example TRIT and the target "anagr开发者_运维技巧amed" string, TIRT.

Objective: We have to output all the valid sequences of 'i' and 'o' (push and pop's, respectively) which produce the target string from the source string.

So, I was thinking of calculate all permutations of "i" and "o" , but cutting this cases:

1) if current permutation begins with an 'o', stop checking, since all the of the next permutations will begin with this pop command and popping something from an empty stack is an invalid command.

2) if an 'o' command is found in the middle of the checking and there is nothing in the stack, skip that case.

3) if an 'i' command is found and there is nothing in the input string, skip that case.

4) if an 'o' command is found and currently expected character is not the character just popped out, then skip that case, since this will never reach to the target string.

5) don't search if the input and target strings have different lengths.

but I think it might get me TLE anyway...

I know the theory: permutations perhaps and backtracking all the way. I just have too many difficulties implementing it.

could anyone please share with me some code and or ideas please?

P.S.: Any suggestion that may decrease some execution time will be welcome , of course.

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

This first iteration solution is instructive. It's not the most efficient since it uses String all over the place, but it's a good place to start.

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