次の字句学的な最短要素の選択

Question

JackとDanielは友達です。どちらも手紙、特に大文字が好きです。 彼らは新聞から大文字を切り取っていて、それぞれが別々の積み重ねて保管された手紙の集まりを持っています。 美しい1日、モルガンはジャックとダニエルを訪れました。彼はそのコレクションを見た。モルガンは、その2つのコレクションからなる辞書編集的に最小限の文字列が何であるか疑問に思った。コレクションの一番上にあるときに手紙を受け取ることができます。 また、Morganは少年のコレクションのすべての文字を使用したいと考えています。

入力形式

最初の行は、テストケース、Tの数を含んでいます。 次の2行には、最初の行に文字列aが含まれ、2行目に文字列bが含まれます。

各行のテストケースごとに、辞書順に最小の文字列を改行して出力します。

サンプル入力

JACK

DANIEL

ABACABA

ABACABA

出力例ここで

DAJACKNIEL

AABABACABACABA

は私のアプローチです：

t = int(raw_input()) 
for _ in range(t): 
    a = raw_input() 
    b = raw_input() 
    i = 0 
    j = 0 
    prev = 0 
    res = "" 
    while i < len(a) and j < len(b): 
     if a[i:] < b[j:]: 
      res += a[i] 
      i += 1 
      prev = 0 
     elif a[i:] > b[j:]: 
      res += b[j] 
      j += 1 
      prev = 1 
     else: 
      if prev == 0: 
       res += a[i] 
       i += 1 
       prev = 0 
      else: 
       res += b[j] 
       j += 1 
       prev = 1 
    print res + a[i:]+b[j:] 

Answer 1

はケースa = "C"とb = "CA"を考えてみましょう。プログラムの出力は"CCA"ですが、正解は"CAC"です。問題は、あなたのコードがよりも"CA"を好むので、"C" < "CA"です。