Interview Question Categories

THREE STRINGS INTERLEAVED PROBLEM

THREE STRINGS INTERLEAVED PROBLEM


//We are given 3 strings: str1, str2, and str3. Str3 is said to be a 
//shuffle of str1 and str2 if it can be formed by interleaving the 
//characters of str1 and str2 in a way that maintains the left to right 
//ordering of the characters from each string. For example, given str1=”abc” 
//and str2=”def”, str3=”dabecf” is a valid shuffle since it preserves the 
//character ordering of the two strings. So, given these 3 strings write 
//a function that detects whether str3 is a valid shuffle of str1 and str2.
namespace ArdenDertat_3StringProb
{
    class Program
    {
        static Boolean CheckForOrderingOfChars(String S1, String S2, String S3)
        {
            int i = 0, j = 0;

            for (int index = 0; index < S3.Length; index++)

            {
                if (i < S1.Length && S3[index] == S1[i])
                    i++;
                else if (j < S2.Length && S3[index] == S2[j])
                    j++;
                else return false;
            }
            return true;
        }

        static void Main(string[] args)

        {
            Console.WriteLine(CheckForOrderingOfChars("abcd","ddef","adbcddef"));
        }
    }
}

2 comments:

  1. This isn't correct. Consider a case like S1 = "abcd", S2 = "aef", s3 = "aebcdf". The answer should be true. However, this algorithm returns false because you check s3[0] = s1[0], which evaluates to true, and so you increment i. Then you check s3[1] = s1[1] which is false. You then check s3[1] = s2[0], which is also false, and you return false.

    This kind of greedy approach won't work. The solution should involve DP.

    ReplyDelete
  2. No The answer should be false, Please go through the question again. In S3, after 'a' there should be either another 'a' or 'b'.

    ReplyDelete