I saw the same sub-problem in LeetCode, and there exists a O(n) neat greedy solution:
for _ in range(int(input())): a = input() + ‘[‘ b = input() + ‘[‘ output = "" for _ in range(len(a) + len(b) - 2): if a < b: output += a[0] a = a[1:] else: output += b[0] b = b[1:] print(output)
Please note: ‘[‘ is the first char after ‘Z‘.
HackerRank "Morgan and a String"
原文：http://www.cnblogs.com/tonix/p/5366382.html