2つのstrを取る再帰関数はソートされたstrを返します

Question

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:]) 

この関数は2つのstrを取り、アルファベット順にstrを返します。例えば：

merge_chars('abxy','lmz') 

戻り

'ablmxyz'. 

再帰を使用する必要があります。

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 

：それは

aaaace 

代わりの

abcdef 

私は以下の記載されてしまったエラーを返しますが

、私の関数は

merge_chars('ace','bdf') 

を呼び出します

誰かにそれを修正する方法を教えてもらえますか？

Answer 1

再帰を使用する場合は、ループを使用する必要はありません。代わりに、各呼び出しで1文字を削除してから再帰します。あなただけの3つのシナリオを以下の誰もがカバーされていることを確認する必要があります。文字列は文字が文字列の

つだけの文字が

両方の文字列を持って残したままにしてい

1. どちらの文字

を残しました

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

出力：ここ

は例です

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