Interleaving String

#Day 9

The interleaving string is a combination of two string such that order of characters in both the string is preserved in the interleaving string.

Example-

One of the interleaving string of “abc and abd is ababcd.

Checking for the interleaving string can be solved in O(nm)  using dynamic programming. Where n is the size of string 1 and m is the size of string 2.

For this, we create a table of size (n+1)*(m+1).

We fill the row 0 and column 0 first and then the rest of the table with the following rule.

  • [rowIndex + columnIndex-1] is the index in interleaving string.
  • rowIndex-1 is the index in string 2.
  • columnIndex -1 is the index in string 1.

We compare Interleaving string index value with string 2 index value and string 1 index value. Then we process it according to the following rule.

  • If interleaving string value == string 1 index value and left column of the field is 1.
    • Then  mark the field with 1
  • ELSE IF  interleaving string value == string 2 index value and  column just above the field is 1.
    • Then  mark the field with 1
  • ElSE:
    • Mark it as 0

On any given position 1 means. That by this point it is true of the interleaving string. And 0 means it is not.

def isInterleaving(stringA,stringB,interleavingString):
    lenStringA = len(stringA)
    lenStringB = len(stringB)
    interleavingTable =constructTable(stringA,stringB,interleavingString,lenStringA,lenStringB)
    for rowIndex in xrange(1,lenStringB+1):
        for columnIndex in xrange(1,lenStringA+1):
            if interleavingString[rowIndex+columnIndex-1]==stringA[columnIndex-1] and interleavingTable[rowIndex][columnIndex-1]==1:
                interleavingTable[rowIndex][columnIndex]=1
            elif interleavingString[rowIndex+columnIndex-1]==stringB[rowIndex-1] and interleavingTable[rowIndex-1][columnIndex]==1:
                interleavingTable[rowIndex][columnIndex]=1
            else:
                interleavingTable[rowIndex][columnIndex] = 0
    return interleavingTable[lenStringB][lenStringA]

Let’s see this with an example-

is1table[0][0] is initialized with 1 because the empty string can be the part of the interleaving string.

IS2.pngis01

string 1[0]==interleavingString[0] and left field is 1

So we mark the current one as 1.

IS3.pngis02

 

IS4.pngIS03.png

Then we fill the column 0 as

IS5.pngis01

 

and the rest of the table is marked with the same rule. And we get the final table as

is6

We Return the table[lastRow][lastColumn] which is 1. Hence the given string is the interleaving string of string 1 and string 2.

Time Complexity

The time complexity of this algorithm is O(nm). n and m are the lengths of string 1 and string 2 respectively.

Source Code

Source code for the implementation of this problem can be found here.

Credits

This article is inspired from the Tushar’s Youtube Channel.

 

Advertisements

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