CODEWITHSUNDEEP
pythonrecursion
Stephan
Stephan

Reputation: 375

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?

Upvotes: 0

Views: 1151

Answers (1)

niemmi
niemmi

Reputation: 17263

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

Upvotes: 1

Related Questions