Pythonで2つの文字列の最大のマージを見つけるプログラム

2つの文字列sとtがあるとします。次の方法でmergeという文字列を作成します。sまたはtのいずれかが空でないときに、次のオプションのいずれかを選択します-

• sが空でない場合は、sの最初の文字を追加してマージし、sから削除します。

• tが空でない場合は、tの最初の文字を追加してマージし、tから削除します。

最後に、形成できる辞書式順序で最大のマージを見つける必要があります。

したがって、入力がs ="zxyxx" t ="yzxxx"の場合、出力は "zyzxyxxxxx"

これを解決するには、次の手順に従います-

• a：=0、b：=0

• マージ：=空白の文字列

• W1：=sのサイズ

• W2：=tのサイズ

• a

  • インデックスaから終了までのsのサブストリング>インデックスbから終了までのtのサブストリングの場合

    • マージ：=連結連結s [a]

      をマージ

    • a：=a + 1

  • それ以外の場合

    • マージ：=連結連結t [b]

      をマージ

    • b：=b + 1

• マージ連結（インデックスaから終了までのsのサブストリング）連結（インデックスbから終了までのtのサブストリング）を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(s, t):
   a = b = 0
   merge = ""

   W1 = len(s)
   W2 = len(t)
   while a < W1 and b < W2:
      if s[a:] > t[b:]:
         merge += s[a]
         a += 1
      else:
         merge += t[b]
         b += 1

   return merge + s[a:] + t[b:]

s = "zxyxx"
t = "yzxxx"
print(solve(s, t))

入力

"zxyxx", "yzxxx"

出力

zyzxyxxxxx