Pythonで1つの文字列を他の文字列のサブ文字列にするために必要な最小数の操作を見つけるプログラム

2つの文字列sとtがあるとすると、sがtをsの部分文字列にするために必要な操作の最小量を見つける必要があります。これで、各操作で、s内の任意の位置を選択し、その位置の文字を他の任意の文字に変更できます。

したがって、入力がs ="abbpqr"、t ="bbxy"の場合、サブストリング "bbpq"を取得して、'p'を'x'に、'q'を'に変更できるため、出力は2になります。 y'。

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

• k：=tのサイズ、n：=sのサイズ
• ans：=10 ^ 10
• 0からn-kの範囲のiの場合、do
  • ss：=s[インデックスiからi+k-1へ]の部分文字列
  • ans：=最小のansとsとtの一致しない文字の数
• 回答を返す

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

例

class Solution:
   def solve(self, s, t):
      k, n = len(t), len(s)
      ans = 10**10
      for i in range(n - k + 1):
         ss = s[i:i+k]
         ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
      return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy"))

入力

"abbpqr", "bbxy"

出力

2