Skip to main content

Find if a string is interleaved of two other strings

Here given code implementation process.

/*
    Java program for
    Find if a string is interleaved of two other strings
*/

import java.util.HashMap;
 
public class Interleaving
{
 
    public  boolean isInterleaved(
        String a, 
        String b, 
        String s,
        HashMap<String, Boolean> dp)
    {
      
        if (a.length() == 0 && 
            b.length() == 0 &&
            s.length() == 0) {
            // When no character remain in a, b, s
            // so s is interleaving of a b 
            return true;
        }
 
        if (s.length() == 0)
        {
            // When source string is empty
            return false;
        }
 
        // Construct new key
        String k = (a + "," + b + "," + s);
 
        if (dp.containsKey(k) == false)
        {

            if((a.length() != 0 && s.charAt(0) == a.charAt(0)) &&
                    isInterleaved(a.substring(1), b, s.substring(1), dp) 
                ||
                (b.length() != 0 && s.charAt(0) == b.charAt(0)) &&
                    isInterleaved(a, b.substring(1), s.substring(1), dp) )
            {
                dp.put(k, true);
            }
            else
            {
                dp.put(k, false);
            }
        }
 
        return dp.get(k);
    }

    // Handles the request to checking interleaved of given a b s
    public void interleaved(String a, String b, String s)
    {
        HashMap<String, Boolean> dp = 
        new HashMap<String, Boolean>();
        
        if (isInterleaved(a, b, s, dp))
        {
            System.out.println(s+" is interleaving of "+a+" and "+b);
        }
        else
        {
            System.out.println(s+" is not interleaving of "+a+" and "+b);
        }
 
    }
 
    public static void main(String[] args)
    {
        Interleaving task = new Interleaving();

        /*
            Example A
            --------------
                a = ACF
                b = HBE
                s = AHBCEF
            ---------------
            Result : True

            because ACF and HBE is subsequence is construct AHBCEF
                    
              A     C   F
                H B   E
            -----------------
              A H B C E F
        */
        task.interleaved("ACF","HBE","AHBCEF");
 
        /*
            Example B
            --------------
            a = ACF
            b = BEH
            s = AHBCEF
            ---------------
            Result : False

             A     C   F
                 B   E   H <- this is not valid
            -----------------
            
            because ACF and HBE is subsequence is can not construct AHBCEF
        */
        task.interleaved("ACF","BEH","AHBCEF");


        /*
            Example C
            --------------
            a = AF
            b = BCDE
            s = ABCDEF
            ---------------
            Result : False

            because AF and BCDE is subsequence is construct ABCDEF
        */
        task.interleaved("AF","BCDE","ABCDEF");

        /*
            Example D
            --------------
            a = APP
            b = LY
            s = APPLY
            ---------------
            Result : True

            because APP and LY is subsequence is construct ABCDEF
        */
        task.interleaved("AF","BCDE","ABCDEF");
    }
}

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
// Include header file
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;
class Interleaving
{
	public: bool isInterleaved(
      string a, 
      string b, 
      string s, 
      unordered_map < string, bool > dp)
	{
		if (a.length() == 0 && b.length() == 0 && s.length() == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.length() == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		string k = (a  +  "," +  b  +  "," +  s);
		if (dp.find(k) != dp.end() == false)
		{
			if ((a.length() != 0 && s[0] == a[0]) 
                && this->isInterleaved(a.substr(1), b, s.substr(1), dp) 
                || 
                (b.length() != 0 && s[0] == b[0]) && 
                this->isInterleaved(a, b.substr(1), s.substr(1), dp))
			{
				dp[k] = true;
			}
			else
			{
				dp[k] = false;
			}
		}
		return dp[k];
	}
	// Handles the request to checking interleaved of given a b s
	void interleaved(string a, string b, string s)
	{
		unordered_map < string, bool > dp;
		if (this->isInterleaved(a, b, s, dp))
		{
			cout << s << " is interleaving of " 
          		 << a << " and " << b << endl;
		}
		else
		{
			cout << s << " is not interleaving of " 
          		 << a << " and " << b << endl;
		}
	}
};
int main()
{
	Interleaving *task = new Interleaving();
	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	task->interleaved("ACF", "HBE", "AHBCEF");
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	task->interleaved("ACF", "BEH", "AHBCEF");
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	task->interleaved("AF", "BCDE", "ABCDEF");
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	task->interleaved("AF", "BCDE", "ABCDEF");
	return 0;
}

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
// Include namespace system
using System;
using System.Collections.Generic;
public class Interleaving
{
	public Boolean isInterleaved(
  	String a, 
   	String b, 
   	String s, 
   	Dictionary < string, bool > dp)
	{
		if (a.Length == 0 && b.Length == 0 && s.Length == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.Length == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		String k = (a + "," + b + "," + s);
		if (dp.ContainsKey(k) == false)
		{
			if ((a.Length != 0 && s[0] == a[0]) && 
                 this.isInterleaved(a.Substring(1), b, s.Substring(1), dp) 
                || 
                (b.Length != 0 && s[0] == b[0]) && 
                 this.isInterleaved(a, b.Substring(1), s.Substring(1), dp))
			{
				dp.Add(k, true);
			}
			else
			{
				dp.Add(k, false);
			}
		}
		return dp[k];
	}
	// Handles the request to checking interleaved of given a b s
	public void interleaved(String a, String b, String s)
	{
		Dictionary < string, bool > dp = new Dictionary < string, bool > ();
		if (this.isInterleaved(a, b, s, dp))
		{
			Console.WriteLine(s + " is interleaving of " + a + " and " + b);
		}
		else
		{
			Console.WriteLine(s + " is not interleaving of " + a + " and " + b);
		}
	}
	public static void Main(String[] args)
	{
		Interleaving task = new Interleaving();
		/*
		    Example A
		    --------------
		        a = ACF
		        b = HBE
		        s = AHBCEF
		    ---------------
		    Result : True
		    because ACF and HBE is subsequence is construct AHBCEF
		            
		      A     C   F
		        H B   E
		    -----------------
		      A H B C E F
		        
		*/
		task.interleaved("ACF", "HBE", "AHBCEF");
		/*
		    Example B
		    --------------
		    a = ACF
		    b = BEH
		    s = AHBCEF
		    ---------------
		    Result : False
		     A     C   F
		         B   E   H <- this is not valid
		    -----------------
		    
		    because ACF and HBE is subsequence is can not construct AHBCEF

		*/
		task.interleaved("ACF", "BEH", "AHBCEF");
		/*
		    Example C
		    --------------
		    a = AF
		    b = BCDE
		    s = ABCDEF
		    ---------------
		    Result : False
		    because AF and BCDE is subsequence is construct ABCDEF

		*/
		task.interleaved("AF", "BCDE", "ABCDEF");
		/*
		    Example D
		    --------------
		    a = APP
		    b = LY
		    s = APPLY
		    ---------------
		    Result : True
		    because APP and LY is subsequence is construct ABCDEF
		        
		*/
		task.interleaved("AF", "BCDE", "ABCDEF");
	}
}

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
package main
import "fmt"
/*
    Go program for
    Find if a string is interleaved of two other strings
*/

func  isInterleaved(a string, b string, s string, dp map[string] bool) bool {
	if len(a) == 0 && len(b) == 0 && len(s) == 0 {
		// When no character remain in a, b, s
		// so s is interleaving of a b
		return true
	}
	if len(s) == 0 {
		// When source string is empty
		return false
	}
	// Construct new key
	var k string = (a + "," + b + "," + s)
	if _, found := dp[k] ; found == false {
		if (len(a) != 0 && s[0] == a[0]) && isInterleaved(a[1:], b, s[1:], dp) || (len(b) != 0 && s[0] == b[0]) && isInterleaved(a, b[1:], s[1:], dp) {
			dp[k] = true
		} else {
			dp[k] = false
		}
	}
	return dp[k]
}
// Handles the request to checking interleaved of given a b s
func interleaved(a, b, s string) {
	var dp = make(map[string] bool)
	if isInterleaved(a, b, s, dp) {
		fmt.Println(s, "is interleaving of ", a, " and ", b)
	} else {
		fmt.Println(s, "is not interleaving of ", a, " and ", b)
	}
}
func main() {

	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	interleaved("ACF", "HBE", "AHBCEF")
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	interleaved("ACF", "BEH", "AHBCEF")
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	interleaved("AF", "BCDE", "ABCDEF")
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	interleaved("AF", "BCDE", "ABCDEF")
}

Output

AHBCEF is interleaving of  ACF  and  HBE
AHBCEF is not interleaving of  ACF  and  BEH
ABCDEF is interleaving of  AF  and  BCDE
ABCDEF is interleaving of  AF  and  BCDE

<?php
/*
    Php program for
    Find if a string is interleaved of two other strings
*/
class Interleaving
{
	public function isInterleaved($a, $b, $s, $dp)
	{
		if (strlen($a) == 0 && strlen($b) == 0 && strlen($s) == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (strlen($s) == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		$k = ($a.",".$b.",".$s);
		if (array_key_exists($k, $dp) == false)
		{
			if ((strlen($a) != 0 && $s[0] == $a[0]) &&
                $this->isInterleaved(substr($a, 1), $b, substr($s, 1) , $dp) || 
                (strlen($b) != 0 && $s[0] == $b[0]) && 
                $this->isInterleaved($a, substr($b, 1), substr($s, 1), $dp))
			{
				$dp[$k] = true;
			}
			else
			{
				$dp[$k] = false;
			}
		}
		return $dp[$k];
	}
	// Handles the request to checking interleaved of given a b s
	public	function interleaved($a, $b, $s)
	{
		$dp = array();
		if ($this->isInterleaved($a, $b, $s, $dp))
		{
			echo($s.
				" is interleaving of ".$a.
				" and ".$b.
				"\n");
		}
		else
		{
			echo($s.
				" is not interleaving of ".$a.
				" and ".$b.
				"\n");
		}
	}
}

function main()
{
	$task = new Interleaving();
	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	$task->interleaved("ACF", "HBE", "AHBCEF");
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	$task->interleaved("ACF", "BEH", "AHBCEF");
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	$task->interleaved("AF", "BCDE", "ABCDEF");
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	$task->interleaved("AF", "BCDE", "ABCDEF");
}
main();

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
/*
    Node JS program for
    Find if a string is interleaved of two other strings
*/
class Interleaving
{
	isInterleaved(a, b, s, dp)
	{
		if (a.length == 0 && b.length == 0 && s.length == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.length == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		var k = (a + "," + b + "," + s);
		if (dp.has(k) == false)
		{
			if ((a.length != 0 && s.charAt(0) == a.charAt(0)) 
                && this.isInterleaved(a.substring(1), b, s.substring(1), dp) 
                || (b.length != 0 && s.charAt(0) == b.charAt(0)) 
                && this.isInterleaved(a, b.substring(1), s.substring(1), dp))
			{
				dp.set(k, true);
			}
			else
			{
				dp.set(k, false);
			}
		}
		return dp.get(k);
	}
	// Handles the request to checking interleaved of given a b s
	interleaved(a, b, s)
	{
		var dp = new Map();
		if (this.isInterleaved(a, b, s, dp))
		{
			console.log(s + " is interleaving of " + a + " and " + b);
		}
		else
		{
			console.log(s + " is not interleaving of " + a + " and " + b);
		}
	}
}

function main()
{
	var task = new Interleaving();
	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	task.interleaved("ACF", "HBE", "AHBCEF");
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	task.interleaved("ACF", "BEH", "AHBCEF");
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
}
main();

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
#    Python 3 program for
#    Find if a string is interleaved of two other strings
class Interleaving :
	def isInterleaved(self, a, b, s, dp) :
		if (len(a) == 0 and len(b) == 0 and len(s) == 0) :
			#  When no character remain in a, b, s
			#  so s is interleaving of a b
			return True
		
		if (len(s) == 0) :
			#  When source string is empty
			return False
		
		#  Construct new key
		k = (a + ","
			+ b + ","
			+ s)
		if ((k in dp.keys()) == False) :
			if ((len(a) != 0 and s[0] == a[0]) and 
            self.isInterleaved(a[1:], b, s[1:], dp) or 
            (len(b) != 0 and s[0] == b[0]) and 
            self.isInterleaved(a, b[1:], s[1:], dp)) :
				dp[k] = True
			else :
				dp[k] = False
			
		
		return dp.get(k)
	
	#  Handles the request to checking interleaved of given a b s
	def interleaved(self, a, b, s) :
		dp = dict()
		if (self.isInterleaved(a, b, s, dp)) :
			print(s ," is interleaving of ", a ," and ", b)
		else :
			print(s ," is not interleaving of ", a ," and ", b)
		
	

def main() :
	task = Interleaving()
	#    Example A
	#    --------------
	#        a = ACF
	#        b = HBE
	#        s = AHBCEF
	#    ---------------
	#    Result : True
	#    because ACF and HBE is subsequence is construct AHBCEF
	#      A     C   F
	#        H B   E
	#    -----------------
	#      A H B C E F
	task.interleaved("ACF", "HBE", "AHBCEF")
	#    Example B
	#    --------------
	#    a = ACF
	#    b = BEH
	#    s = AHBCEF
	#    ---------------
	#    Result : False
	#     A     C   F
	#         B   E   H <- this is not valid
	#    -----------------
	#    because ACF and HBE is subsequence is can not construct AHBCEF
	task.interleaved("ACF", "BEH", "AHBCEF")
	#    Example C
	#    --------------
	#    a = AF
	#    b = BCDE
	#    s = ABCDEF
	#    ---------------
	#    Result : False
	#    because AF and BCDE is subsequence is construct ABCDEF
	task.interleaved("AF", "BCDE", "ABCDEF")
	#    Example D
	#    --------------
	#    a = APP
	#    b = LY
	#    s = APPLY
	#    ---------------
	#    Result : True
	#    because APP and LY is subsequence is construct ABCDEF
	task.interleaved("AF", "BCDE", "ABCDEF")

if __name__ == "__main__": main()

Output

AHBCEF  is interleaving of  ACF  and  HBE
AHBCEF  is not interleaving of  ACF  and  BEH
ABCDEF  is interleaving of  AF  and  BCDE
ABCDEF  is interleaving of  AF  and  BCDE
#    Ruby program for
#    Find if a string is interleaved of two other strings
class Interleaving 
	def isInterleaved(a, b, s, dp) 
		if (a.length == 0 && b.length == 0 && s.length == 0) 
			#  When no character remain in a, b, s
			#  so s is interleaving of a b
			return true
		end

		if (s.length == 0) 
			#  When source string is empty
			return false
		end

		#  Construct new key
		k = (a + ","
			+ b + ","
			+ s)
		if (dp.key?(k) == false) 
			if ((a.length != 0 && s[0] == a[0]) && 
          self.isInterleaved(a[1..-1], b, s[1..-1], dp) || 
          (b.length != 0 && s[0] == b[0]) && 
          self.isInterleaved(a, b[1..-1], s[1..-1], dp)) 
				dp[k] = true
			else
 
				dp[k] = false
			end

		end

		return dp[k]
	end

	#  Handles the request to checking interleaved of given a b s
	def interleaved(a, b, s) 
		dp = Hash.new()
		if (self.isInterleaved(a, b, s, dp)) 
			print(s ," is interleaving of ", a ," and ", b, "\n")
		else
 
			print(s ," is not interleaving of ", a ," and ", b, "\n")
		end

	end

end

def main() 
	task = Interleaving.new()
	#    Example A
	#    --------------
	#        a = ACF
	#        b = HBE
	#        s = AHBCEF
	#    ---------------
	#    Result : True
	#    because ACF and HBE is subsequence is construct AHBCEF
	#      A     C   F
	#        H B   E
	#    -----------------
	#      A H B C E F
	task.interleaved("ACF", "HBE", "AHBCEF")
	#    Example B
	#    --------------
	#    a = ACF
	#    b = BEH
	#    s = AHBCEF
	#    ---------------
	#    Result : False
	#     A     C   F
	#         B   E   H <- this is not valid
	#    -----------------
	#    because ACF and HBE is subsequence is can not construct AHBCEF
	task.interleaved("ACF", "BEH", "AHBCEF")
	#    Example C
	#    --------------
	#    a = AF
	#    b = BCDE
	#    s = ABCDEF
	#    ---------------
	#    Result : False
	#    because AF and BCDE is subsequence is construct ABCDEF
	task.interleaved("AF", "BCDE", "ABCDEF")
	#    Example D
	#    --------------
	#    a = APP
	#    b = LY
	#    s = APPLY
	#    ---------------
	#    Result : True
	#    because APP and LY is subsequence is construct ABCDEF
	task.interleaved("AF", "BCDE", "ABCDEF")
end

main()

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE

import scala.collection.mutable._;
/*
    Scala program for
    Find if a string is interleaved of two other strings
*/
class Interleaving()
{
	def isInterleaved(
      a: String, 
      b: String, 
      s: String, 
      dp: HashMap[String, Boolean]): Boolean = {
		if (a.length() == 0 && b.length() == 0 && s.length() == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.length() == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		var k: String = (a + "," + b + "," + s);
		if (dp.contains(k) == false)
		{
			if ((a.length() != 0 
                 && s.charAt(0) == a.charAt(0)) 
                && isInterleaved(a.substring(1), b, s.substring(1), dp) 
                || 
                (b.length() != 0 
                 && s.charAt(0) == b.charAt(0)) 
                && isInterleaved(a, b.substring(1), s.substring(1), dp))
			{
				dp.addOne(k, true);
			}
			else
			{
				dp.addOne(k, false);
			}
		}
		return dp.get(k).get;
	}
	// Handles the request to checking interleaved of given a b s
	def interleaved(a: String, b: String, s: String): Unit = {
		var dp: HashMap[String, Boolean] = new HashMap[String, Boolean]();
		if (isInterleaved(a, b, s, dp))
		{
			println(s + " is interleaving of " + a + " and " + b);
		}
		else
		{
			println(s + " is not interleaving of " + a + " and " + b);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Interleaving = new Interleaving();
		/*
		    Example A
		    --------------
		        a = ACF
		        b = HBE
		        s = AHBCEF
		    ---------------
		    Result : True
		    because ACF and HBE is subsequence is construct AHBCEF
		            
		      A     C   F
		        H B   E
		    -----------------
		      A H B C E F
		        
		*/
		task.interleaved("ACF", "HBE", "AHBCEF");
		/*
		    Example B
		    --------------
		    a = ACF
		    b = BEH
		    s = AHBCEF
		    ---------------
		    Result : False
		     A     C   F
		         B   E   H <- this is not valid
		    -----------------
		    
		    because ACF and HBE is subsequence is can not construct AHBCEF

		*/
		task.interleaved("ACF", "BEH", "AHBCEF");
		/*
		    Example C
		    --------------
		    a = AF
		    b = BCDE
		    s = ABCDEF
		    ---------------
		    Result : False
		    because AF and BCDE is subsequence is construct ABCDEF

		*/
		task.interleaved("AF", "BCDE", "ABCDEF");
		/*
		    Example D
		    --------------
		    a = APP
		    b = LY
		    s = APPLY
		    ---------------
		    Result : True
		    because APP and LY is subsequence is construct ABCDEF
		        
		*/
		task.interleaved("AF", "BCDE", "ABCDEF");
	}
}

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
/*
    Kotlin program for
    Find if a string is interleaved of two other strings
*/
class Interleaving
{
	fun isInterleaved(a: String, b: String, s: String, dp: MutableMap < String, Boolean > ): Boolean
	{
		if (a.length == 0 && b.length == 0 && s.length == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.length == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		val k: String = (a + "," + b + "," + s);
		if (dp.containsKey(k) == false)
		{
			if ((a.length != 0 && s.get(0) == a.get(0)) && this.isInterleaved(a.substring(1), b, s.substring(1), dp) || (b.length != 0 && s.get(0) == b.get(0)) && this.isInterleaved(a, b.substring(1), s.substring(1), dp))
			{
				dp.put(k, true);
			}
			else
			{
				dp.put(k, false);
			}
		}
		return dp.getValue(k);
	}
	// Handles the request to checking interleaved of given a b s
	fun interleaved(a: String, b: String, s: String): Unit
	{
		var dp = mutableMapOf < String, Boolean > ();
		if (this.isInterleaved(a, b, s, dp))
		{
			println(s + " is interleaving of " + a + " and " + b);
		}
		else
		{
			println(s + " is not interleaving of " + a + " and " + b);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Interleaving = Interleaving();
	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	task.interleaved("ACF", "HBE", "AHBCEF");
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	task.interleaved("ACF", "BEH", "AHBCEF");
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
}

Output

AHBCEF is interleaving of ACF and HBE
AHBCEF is not interleaving of ACF and BEH
ABCDEF is interleaving of AF and BCDE
ABCDEF is interleaving of AF and BCDE
import Foundation;
/*
    Swift 4 program for
    Find if a string is interleaved of two other strings
*/
class Interleaving
{
  	
  	func substring(_ text : String) -> String
  	{
  		let arr = Array(text);
  		var n  = text.count-1;
  		var ans = "";
  		while(n >= 1)
  		{
  			ans += String(arr[n]);
  			n-=1;
  		}

  		return ans;
  	}
	func isInterleaved(_ a: String, _ b: String, _ s: String, _ dp: inout[
                        String : Bool ]) -> Bool
	{
		if (a.count == 0 && b.count == 0 && s.count == 0)
		{
			// When no character remain in a, b, s
			// so s is interleaving of a b
			return true;
		}
		if (s.count == 0)
		{
			// When source string is empty
			return false;
		}
		// Construct new key
		let k: String = (a + "," + b + "," + s);
		if (dp.keys.contains(k) == false)
		{
			if ((a.count  != 0 && Array(s)[0] == Array(a)[0]) && self.isInterleaved(substring(a), b, substring(s), &dp) || (b.count  != 0 && Array(s)[0] == Array(b)[0]) && 
			self.isInterleaved(a, substring(b), substring(s), &dp))
			{
				dp[k] = true;
			}
			else
			{
				dp[k] = false;
			}
		}
		return dp[k]!;
	}
	// Handles the request to checking interleaved of given a b s
	func interleaved(_ a: String, _ b: String, _ s: String)
	{
		var dp = [String : Bool]();
		if (self.isInterleaved(a, b, s, &dp))
		{
			print(s ," is interleaving of ", a ," and ", b);
		}
		else
		{
			print(s ," is not interleaving of ", a ," and ", b);
		}
	}
}
func main()
{
	let task: Interleaving = Interleaving();
	/*
	    Example A
	    --------------
	        a = ACF
	        b = HBE
	        s = AHBCEF
	    ---------------
	    Result : True
	    because ACF and HBE is subsequence is construct AHBCEF
	            
	      A     C   F
	        H B   E
	    -----------------
	      A H B C E F
	        
	*/
	task.interleaved("ACF", "HBE", "AHBCEF");
	/*
	    Example B
	    --------------
	    a = ACF
	    b = BEH
	    s = AHBCEF
	    ---------------
	    Result : False
	     A     C   F
	         B   E   H <- this is not valid
	    -----------------
	    
	    because ACF and HBE is subsequence is can not construct AHBCEF

	*/
	task.interleaved("ACF", "BEH", "AHBCEF");
	/*
	    Example C
	    --------------
	    a = AF
	    b = BCDE
	    s = ABCDEF
	    ---------------
	    Result : False
	    because AF and BCDE is subsequence is construct ABCDEF

	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
	/*
	    Example D
	    --------------
	    a = APP
	    b = LY
	    s = APPLY
	    ---------------
	    Result : True
	    because APP and LY is subsequence is construct ABCDEF
	        
	*/
	task.interleaved("AF", "BCDE", "ABCDEF");
}
main();

Output

AHBCEF  is interleaving of  ACF  and  HBE
AHBCEF  is not interleaving of  ACF  and  BEH
ABCDEF  is interleaving of  AF  and  BCDE
ABCDEF  is interleaving of  AF  and  BCDE
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment