Pythonで指定された2つの文字列の最大長のマージを取得するプログラム

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

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

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

したがって、辞書式順序で最大のマージを見つける必要があります。

したがって、入力がs ="zxyxx" t ="yzxxx"の場合、出力はzyzxyxxxxxになります。

• sから選択：merge ="z"、s ="xyxx"、t ="yzxxx"

• tから選択：merge ="zy"、s ="xyxx"、t ="zxxx"

• tから選択：merge ="zyz"、s ="xyxx"、t ="xxx"

• sから選択：merge ="zyzx"、s ="yxx"、t ="xxx"

• sから選択：merge ="zyzxy"、s ="xx"、t ="xxx"

次に、マージの最後にsとtの残りの5つのxを追加します。

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

• ans：=空白の文字列

• idx1：=0、idx2：=0

• idx1

  • s [idx1]> t [idx2]または（s[idx1]はt[idx2]と同じであり、s[インデックスidx1から終了]>=t[インデックスidx2から終了]のサブ文字列）の場合、

    • ans：=ans concatenate s [idx1]

    • idx1：=idx1 + 1

  • それ以外の場合、s [idx1]

    • ans：=ans concatenate t [idx2]

    • idx2：=idx2 + 1

• 戻り値ansconcatenates[インデックスidx1から終了]concatenatet[インデックスidx2から終了]

例

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

def solve(s, t):
   ans = ""
   idx1 = idx2 = 0
   while(idx1<len(s) and idx2<len(t)):
      if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
         ans+=s[idx1]
         idx1+=1
      elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
         ans+=t[idx2]
         idx2+=1

   return ans+s[idx1:]+t[idx2:]

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

入力

[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]

出力

zyzxyxxxxx