Pythonで最大k文字を削除した後に回文が形成されるかどうかをチェックするプログラム

文字列sがあるとすると、最大k文字を削除した後、この文字列を回文にすることができるかどうかを確認する必要があります。

したがって、入力がs ="lieuvrel"、k =4の場合、出力はTrueになり、3文字を削除して、回文の「レベル」を取得できます。

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

• 関数lcs（）を定義します。これにはa、bが必要です
• m：=aのサイズ、n：=bのサイズ
• table：=サイズ（m + 1）x（n + 1）の行列で、0で埋めます
• 1からmの範囲のiについては、
  • 1からnの範囲のjについては、
    • a[i-1]がb[j-1]と同じ場合、
      • table [i、j]：=1 + table [i-1、j-1]
    • それ以外の場合、
      • table [i、j]：=table [i、j-1]とtable [i-1、j]の最大値
• return table [m、n]
• メインの方法から次の手順を実行します。
• （sのサイズ-lcs（s、sの逆）<=k）の場合はtrueを返し、それ以外の場合はfalseを返します

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

例

class Solution:
   def solve(self, s, k):
      def lcs(a, b):
         m, n = len(a), len(b)
         table = [[0] * (n + 1) for _ in range(m + 1)]
         for i in range(1, m + 1):
            for j in range(1, n + 1):
               if a[i - 1] == b[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
               else:
                  table[i][j] = max(table[i][j - 1], table[i - 1][j])
         return table[m][n]

      return len(s) - lcs(s, s[::-1]) <= k
     
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

入力

"lieuvrel", 4

出力

True