Find if a string is formed by interleaving two strings

Table of Contents

Find if a string is formed by interleaving two strings

Problem: Given a string 's' and two candidate strings 's1' and 's2', find if 's' is formed by interleaving of 's1' and 's2'.
Interleaving is defined as formed by picking characters randomly from s1 and s2 but preserving the order of characters in s1 and s2.

Example: If s1 = 'ABC' and s2 = 'def', then 'AdBeCf' is an interleaved string.
'ABCdef' is also an interleaved string and so is 'ABdeCf'.
'AdefCB' is not an interleaved string because the order of 'BC' is not maintained.

Solution:
A recursive solution for this is as follows:


public class StringInterleaving {
    
    public static void main (String args[])
    {
        String s1 = "Hello";
        String s2 = "Wo";
        
        String s = "HWelolo";
        
        System.out.println(isInterleaved (s1, s2, s, 0, 0, 0));
    }

    private static boolean isInterleaved
    (
        String s1, String s2, String s, 
        int pos1, int pos2, int pos
    ) {

        System.out.println(s1.substring(pos1) + "," +
                           s2.substring(pos2) + "," +
                           s.substring(pos));
        
        if (pos >= s.length())
            return true;
        
        boolean match1 = false;
        boolean match2 = false;
        
        if (pos1 < s1.length())
            match1 = (s.charAt(pos) == s1.charAt(pos1));
        
        if (pos2 < s2.length())
            match2 = (s.charAt(pos) == s2.charAt(pos2));
        
        return (
                (match1 && isInterleaved (s1, s2, s, pos1+1, pos2, pos+1)) ||
                (match2 && isInterleaved (s1, s2, s, pos1, pos2+1, pos+1))
            );
        
    }

}

Example executions

Input:
s1 = "ABC"
s2 = "def"
s = "AdeBCf"

Execution:

ABC,def,AdeBCf
BC,def,deBCf
BC,ef,eBCf
BC,f,BCf
C,f,Cf
,f,f
,,
true

Input:
s1 = "ape"
s2 = "aple"
s = "aplee"

Execution:

ape,aple,aplee
pe,aple,plee
e,aple,lee
ape,ple,plee
ape,le,lee
ape,e,ee
ape,,e
false

Execution for complex strings:
Input:
s1 = "rats"
s2 = "rat_rats_rat_"
s = "rat_rats_rat_rats"

Execution:

rats,  rat_rats_rat_,  rat_rats_rat_rats
ats,  rat_rats_rat_,  at_rats_rat_rats
ts,  rat_rats_rat_,  t_rats_rat_rats
s,  rat_rats_rat_,  _rats_rat_rats

rats,  at_rats_rat_,  at_rats_rat_rats
rats,  t_rats_rat_,  t_rats_rat_rats
rats,  _rats_rat_,  _rats_rat_rats
rats,  rats_rat_,  rats_rat_rats
ats,  rats_rat_,  ats_rat_rats
ts,  rats_rat_,  ts_rat_rats
s,  rats_rat_,  s_rat_rats
,  rats_rat_,  _rat_rats

rats,  ats_rat_,  ats_rat_rats
rats,  ts_rat_,  ts_rat_rats
rats,  s_rat_,  s_rat_rats
rats,  _rat_,  _rat_rats
rats,  rat_,  rat_rats
ats,  rat_,  at_rats
ts,  rat_,  t_rats
s,  rat_,  _rats

rats,  at_,  at_rats
rats,  t_,  t_rats
rats,  _,  _rats
rats,  ,  rats
ats,  ,  ats
ts,  ,  ts
s,  ,  s
,  ,  
true

Clearly, this can be optimized by dynamic programming because its calculating subproblems over and over again.

Dynamic Programming Solution

boolean isInterleaved(String A, String B, String C)
{
    int M = A.length();
    int N = B.length();
 
    if ((M+N) != C.length())
       return false;
 
    // lookup[i][j] is true if C[0..i+j-1] is an interleaving of A[0..i-1] and B[0..j-1].
    boolean lookup[][] = new boolean[M+1][N+1];
 

    for (int i=0; i<=M; i++)
    {
        for (int j=0; j<=N; j++)
        {
            // If both A and B are empty, then C must also be empty (due to length matching)
            // And since one empty string is interleaving of other two empty
            // strings, lookup[0][0] is true.
            if (i==0 && j==0)
                lookup[i][j] = true;
 
            // If A is empty, check one-to-one match with B
            else if (i==0 && B[j-1]==C[j-1])
                lookup[i][j] = lookup[i][j-1];
 
            // If B is empty, check one-to-one match with A
            else if (j==0 && A[i-1]==C[i-1])
                lookup[i][j] = lookup[i-1][j];
 

            // Regular check for interleaving

            if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
                lookup[i][j]=(lookup[i-1][j] || lookup[i][j-1]);

            else if(A[i-1]==C[i+j-1])
                lookup[i][j] = lookup[i-1][j];
 
            else if (B[j-1]==C[i+j-1])
                lookup[i][j] = lookup[i][j-1];

            // Its too soon to return a false if C[i+j-1] matches neither A or B.
            // Think why?
        }
    }
 
    return lookup[M][N];
}

Explanation for lines 43 and 44

Check the loops in the dynamic programming solution.
The first loop compares a part of first string with the complete second string.
If first loop is at an index 'k', it is possible that the interleaved string has a first string character on position 'k+1'
Since the loop is not allowing the first string to be completely visible (except in the last pass), it's not correct to terminate if 'k+1'^th character does not match.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email:	(Your email is not shared with anybody)

Comment:

Facebook comments:

Site Owner: Sachin Goyal