pythonlexicographic

How to do this Lexicography Lc problem the right way


I'm attempting to solve a practice leetcode problem with the question is to merge each first individual characters of the 2 string that have smaller lexicography order into a string, here is an example of it.enter image description here

And here is what I tried:

def solution(s1, s2):
    s1=list(s1);s2=list(s2)
    res=[]
    while(1):
        if len(s1)==0:
            res+=s2
            return ''.join(res)
        elif len(s2)==0:
            res+=s1
            return ''.join(res)
        else:
            if s1[0]< s2[0]:
                res.append(s1[0])
                s1.remove(s1[0])
            else:
                res.append(s2[0])
                s2.remove(s2[0])

The test run came out quite weird since I was right on some cases but wrong on others (Right on (s1:'super',s2:'tower' ==> 'stouperwer' ) as expected) but things like (s1: "enbvszyppzyiydnc" s2:"ousswsbeljamma") turn out to be different (Right answer:"eounbvszsswsbeljammayppzyiydnc", My output:"enboussvswsbeljammazyppzyiydnc"). Perhaps, I miss understood the lexicography thing somewhere. Can you guys please let me know? Thank you!


Solution

  • You can use ord to compare two strings.

    def solution(s1, s2):
        s1, s2 = list(reversed(s1)), list(reversed(s2))
        result = []
        while min(len(s1), len(s2)):
            if ord(s1[-1]) <= ord(s2[-1]): result.append(s1.pop())
            else: result.append(s2.pop())
        return "".join(result + list(reversed(s1 + s2)))
    

    Using reversed means that instead of repeatedly removing the first digit, which would take O(n^2) if you keep doing it, you can only go through the process once.

    Also, you are using < to compare the strings, but as the diagram instructs, the priority comes from the first list, so it should be <=.