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
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