Three strings are given a, b, and c. Initially strings b and c are empty.
we have to make string c using following moves:
move1: we can move first character of string a and append to string b
or
move2: we can move last character of string b and append to string c
there would be multiple possible string by following these two rules but we have to return one according to lexical order.

Example:
given: a = 'dad', b="" , c= ""
one possible approach:

1. get a[0] and append to b. so strings became: a = "ad", b = 'd', c=''
   
2. a[0] to string b : a = 'd', b = 'da', c = ''
3. b[-1] to string c : a = 'd', b='d', c = 'a'
4. a[0] to string b : a='', b='dd', c ='a'
5. b[-1] to string c : a='', b='d', c='ad'
6. b[-1] to string c : a='', b='', c='add' so here c = 'add' other answer is also possible but we have to return one which come first in lexicographical order. so 'add' would be ans to this example.
   
   can you please help me to achieve this goal?
   my code:
   

class Solution:
    def solve(self, input1: int, input2: str) -> str:
        res = []
        def rec(st1,st2, st3):
            if not st1 and not st2:
                res.append(st3[:])
                return
            
            if st1:
                rec(st1[1:], st2 st[0], st3)
            if st:
                rec(st1, st2[:len(st2)-1], st3 st2[-1])
        rec(input2, "", "")
        res.sort()
        return res[0]

Not able to pass the test cases with this code.
Note: This question was asked in Amazon ML summer school test 2022 which was scheduled yesterday 7pm - 8pm(India), I asked this question after completion of test and I'm curious to know answer because my code didn't work properly. I wrote the above code for the question but it passed only 4/10 testcases and also didn't show the error, so I'm confused about working of my code.

CodePudding user response：

The problem is you sort your list of res but you don't check if each solution is sorted in lexicographical order.

little changes of your function (and without class):

def solve(input2: str) -> str:
    res = []
    def rec(st1, st2, st3):
        if not st1 and not st2:
            res.append(st3[:])
            return

        if st1:
            rec(st1[1:], st2 st1[0], st3)
        if st2:
            rec(st1, st2[:len(st2)-1], st3 st2[-1])
    rec(input2, "", "")
    print(res)
    sorted_res = sorted(res)
    print('sorted_res: ', sorted_res)
    filtered_res = [x for x in res if x == ''.join(sorted(x))]
    print('filtered_res: ', filtered_res)

Given the example solve(num), the output is:

['mun', 'umn', 'unm', 'nmu', 'num']
sorted_res:  ['mun', 'nmu', 'num', 'umn', 'unm']
filtered_res:  []

The line of code filtered_res = ... checks each string in the list whether it is in lexicographical order or not. You would just return res[0] which is wrong here, because mun is no valid answer. For this word there is no valid answer (because filtered_res is an empty list, given your code does follow the rules correctly).