Stephan Stephan - 1 month ago 10
Python Question

recursion function that takes two str return a sorted str

def merge_chars(a : str, b : str) -> str:
if a == '':
return b
if b == '':
return a

for x in a:
for y in b:
if x > y:
return y + merge_chars(a[1:],b)
elif x < y:
return x + merge_chars(a,b[1:])


This function takes two str, and return a str in alphabetic order. for example:

merge_chars('abxy','lmz')


returns

'ablmxyz'.


using recursion is a requirement.

however, when my function calls

merge_chars('ace','bdf')


it returns

aaaace


instead of

abcdef


the error I got is listed below:

39 # Test merge_chars
43 *Error: merge_chars('ace','bdf') -> aaaace but should -> abcdef
44 *Error: merge_chars('abc','xyz') -> aaaabc but should -> abcxyz
45 *Error: merge_chars('abxy','lmzzz') -> aaaaaabxy but should -> ablmxyzzz
46 *Error: merge_chars('acdeghilmnosu','bfjkpqrtvwxyz') -> aaaaaaaaaaaaaacdeghilmnosu but should -> abcdefghijklmnopqrstuvwxyz
47 *Error: merge_chars('bcgprvyz','adefhijklmnoqstuwx') -> aaaaaaaaadefhijklmnoqstuwx but should -> abcdefghijklmnopqrstuvwxyz
48 *Error: merge_chars('cdefghijklmnpqrstuvw','aboxyz') -> aaaaaaaaaaaaaaaaaaaaaboxyz but should -> abcdefghijklmnopqrstuvwxyz
51 *Error: merge_chars(''.join(sorted(l[:13])), ''.join(sorted(l[13:]))) -> aaaaaaaaaaaaaabcdgjlnpqrtz but should -> abcdefghijklmnopqrstuvwxyz


can someone tell me how to fix it?

Answer

If you want to use recursion you don't need to use loops. Instead just remove one character on each call and then recurse. You just need to make sure that everyone of following three scenarios are covered:

  1. Neither of the strings have characters left
  2. Only one of the strings has characters left
  3. Both strings have characters left

Here's example:

def merge_chars(a, b):
    # Base case
    if not a and not b:
        return ''

    if a and (not b or a[0] <= b[0]):
        return a[0] + merge_chars(a[1:], b)
    else:
        return b[0] + merge_chars(a, b[1:])

CASES = [
    ('ace', 'bdf'),
    ('abc', 'xyz'),
    ('abxy', 'lmzzz'),
    ('acdeghilmnosu', 'bfjkpqrtvwxyz'),
    ('bcgprvyz', 'adefhijklmnoqstuwx'),
    ('cdefghijklmnpqrstuvw', 'aboxyz')
]

for x, y in CASES:
    print('{} & {} -> {}'.format(x, y, merge_chars(x, y)))

Output:

ace & bdf -> abcdef
abc & xyz -> abcxyz
abxy & lmzzz -> ablmxyzzz
acdeghilmnosu & bfjkpqrtvwxyz -> abcdefghijklmnopqrstuvwxyz
bcgprvyz & adefhijklmnoqstuwx -> abcdefghijklmnopqrstuvwxyz
cdefghijklmnpqrstuvw & aboxyz -> abcdefghijklmnopqrstuvwxyz
Comments