Print all interleavings of given two strings

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    class Program
    {
        public static ArrayList distinctStrings = new ArrayList();
        static void Main(string[] args)
        {
            string str1 = "abc";
            string str2 = "a2c";
            GenerateInterLeaving(str1, str2, 0, 0, "");
            Console.WriteLine("Total number of interleaving strings generated = " + distinctStrings.Count);
        }
        
        public static void GenerateInterLeaving(string str1, string str2, int pointer1, int pointer2, string result)
        {
            if (result.Length == str1.Length + str2.Length)
            {
                if (!distinctStrings.Contains(result))
                {
                    distinctStrings.Add(result);
                    Console.WriteLine(result);
                    return;
                }
            }
            else
            {
                if (pointer1 < str1.Length)
                {
                    GenerateInterLeaving(str1, str2, pointer1 + 1, pointer2, result + str1[pointer1].ToString());
                }
                if (pointer2 < str2.Length)
                {
                    GenerateInterLeaving(str1, str2, pointer1, pointer2 + 1, result + str2[pointer2].ToString());
                }
            }
        }
    }
}

Output
=======
abca2c
abac2c
aba2cc
aabc2c
aab2cc
aa2bcc
aa2cbc
a2abcc
a2acbc
a2cabc
Total number of interleaving strings generated = 10
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s