Problem Definition:
You are challenged to write an algorithm to check if a given string, s
, can be formed from two other strings, part1
and part2
.
The restriction is that the characters in part1
and part2
are in the same order as in s
.
Test Cases:
- s = “Bananas from Bahamas” ; part1 =”Bahas” ; part2 =” Bananas from am”
- s =”Can we merge it? Yes, we can!”; part1=” an mrgei? e,we”; part2=”C wee tYs can!”
- s=”Making progress; part1=”Mak pross”; part2=”inggre”
- s=’codewars’; part1=’code’; part2=’wars’
- s=’codewars’; part1=’cdw’; part2=’oears’
Logic:
- Start matching character by character, there are two possibilities to start
- ‘s’ with ‘part1’
- ‘s’ with ‘part2’
- ‘s’ with part1: Start matching string ‘s’ in part1 as long it matches and then move to part2 as long as it matches there. come back to part1 and try to match as much it matches then move to part2 … till the end of string ‘s’. If we can’t make progress then return False.
- ‘s’ with part2 : If step2 fails, then start matching ‘s’ with part2…
- It is not just two possibilities, for every character match there are two possibilities, so we need to handle all those cases.
- For example:
- s = “Bananas from Bahamas” ; part1 =”Bahas” ; part2 =” Bananas from am”
- For first character ‘B’ from s, two possibilities s[0] == p1[0], s[0] == p2[0]. ‘s’ matches with ‘p1’ till “Ba”. The rest of ‘s’ (“nanas from Bahamas”) does not match with p2 (“Bananas from am”) . so we have try with second possibility, s[0] == p2[0], this matches till “Bananas from ” in p2. The rest of ‘s’ (“Bahamas”) does not match with p2 (“am”). Then try to match “Bahamas” with p1 (“Bahas”), p2(“am”).
- s=”Bahamas”, p1=”Bahas”, p2=”am”. comparisons should go like this:
'B' in s and 'B' in p1 (1)
'a' in s and 'a' in p1 (2)
'h' in s and 'h' in p1 (3)
'a' in s and 'a' in p1 (False)
'm' in s and 's' in p1 (False)
'm' in s and 'a' in p2 (False)
'a' in s and 'a' in p2 (True) (4)
'm' in s and 'a' in p1 (False)
'm' in s and 'm' in p2
'a' in s and 'a' in p1
's' in s and 's' in p1
'' in s and '' in p1 (True) (5)
True value is bubbles up to (1) . In the order of 5,4,3,2,1
Python code:
Recursive solution:
def is_merge(s, part1, part2):
if not part1:
return s == part2
if not part2:
return s == part1
if not s:
return part1 + part2 == ''
if s[0] == part1[0] and is_merge(s[1:], part1[1:], part2):
return True
if s[0] == part2[0] and is_merge(s[1:], part1, part2[1:]):
return True
return False
Iterative Solution:
def is_merge(s, part1, part2):
queue = [(s,part1,part2)]
while queue:
str, p1, p2 = queue.pop()
if str:
if p1 and str[0] == p1[0]:
queue.append((str[1:], p1[1:], p2))
if p2 and str[0] == p2[0]:
queue.append((str[1:], p1, p2[1:]))
else:
if not p1 and not p2:
return True
return False