Good string programming puzzle

Posted on by

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:

  1. s = “Bananas from Bahamas” ;  part1 =”Bahas” ; part2 =” Bananas from am”
  2. s =”Can we merge it? Yes, we can!”; part1=” an mrgei? e,we”; part2=”C wee tYs can!”
  3. s=”Making progress; part1=”Mak pross”; part2=”inggre”
  4. s=’codewars’; part1=’code’; part2=’wars’
  5. s=’codewars’; part1=’cdw’; part2=’oears’

 

Logic:

  1. Start matching character by character, there are two possibilities to start
    1. ‘s’ with ‘part1’
    2. ‘s’ with ‘part2’
  2. ‘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.
  3. ‘s’ with part2 :  If step2 fails, then start matching ‘s’ with part2…
  4. It is not just two possibilities, for every character match there are two possibilities, so we need to handle all those cases.
  5. For example:
    1. s = “Bananas from Bahamas” ;  part1 =”Bahas” ; part2 =” Bananas from am”
  7. 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”).
  8.    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

Leave a comment