最初または最後から削除してPythonに再度挿入することでターゲットを作成するプログラム

2つの文字列SとTがあり、それらが互いに順列であるとします。 Sの最初または最後の文字を削除して、文字列の任意の場所に挿入する操作があるとします。次に、SをTに変換するために必要な操作の最小数を見つけます。

したがって、入力がs ="zyvxw" t ="vwxyz"の場合、出力は3になります。これらの操作は次のとおりです。「w」を削除し、「v」の後に挿入して「zyvwx」を削除します。「z」を削除します。 「x」の後に挿入して「yvwxz」を取得します。「y」を削除し、「x」の後に挿入して「vwxyz」を取得します。

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

• ans：=sのサイズ、n：=sのサイズ

• 0からn-1の範囲のiの場合、実行

  • k：=0

  • iからn-1の範囲のjの場合、実行

    • kからtのサイズまでの範囲のkについては、次のようにします

      • s[j]がt[k]と同じ場合、

        • ans：=ansとnの最小値-（j --i + 1）

        • ループから出てきます

    • k：=k + 1

  • ansを返す

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

例

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

入力

"zyvxw", "vwxyz"

出力

5