We have 2 strings, say "JACK" and "DANIELS". We create two stacks from these strings, and then loop over them comparing first elements: whichever of the 2 goes first in lexicographic order gets popped from its stack and added to a string (the second value is left alone). So it goes, until we end up with a string containing all the elements from both stacks. In this example it would be "DAJACKNIELS"
My solution takes advantage of the fact that
min function, when applied to
deque() objects, returns the one whose first element goes lexicographically first. As it happens, it works well enough for small testcases, but fails large ones, for it takes all the memory it can get and then some.
Perhaps, something can be improved in my code, or there's a better solution altogether (like, without a
def morgan(a, b): string = "" stack_a = deque() stack_b = deque() stack_a.extend(a) stack_b.extend(b) while True: if len(stack_a) != 0 and len(stack_b) != 0: if stack_a == min(stack_a, stack_b): string += stack_a.popleft() else: string += stack_b.popleft() elif len(stack_a) == 0 and len(stack_b) == 0: break elif len(stack_a) == 0: string += stack_b.popleft() elif len(stack_b) == 0: string += stack_a.popleft() return(string)
Example of a large testcase:
string a: https://pastebin.com/raw/pebMbcA6 string b: https://pastebin.com/raw/bwNEqJcr