Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで文字列回文を作成するために必要な最小文字数をチェックするプログラム

文字列sがあるとすると、文字列が回文になるように挿入する必要のある最小文字数を見つける必要があります。

したがって、入力がs ="mad"の場合、出力は2になります。これは、"am"を挿入して"madam"を取得できるためです。

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

  • 関数dp（）を定義します。これにはi、jが必要です

  • i> =jの場合、

    • 0を返す

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

    • dp（i + 1、j-1）を返す

  • それ以外の場合

    • dp（i + 1、j）およびdp（i、j-1）+1の最小値を返します

  • メインの方法から、次のようにします

  • dp（0、sのサイズ-1）を返す

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

例

class Solution:
   def solve(self, s):
      def dp(i, j):
         if i >= j:
            return 0
         if s[i] == s[j]:
            return dp(i + 1, j - 1)
         else:
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
      return dp(0, len(s) - 1)
ob = Solution()
s = "mad"
print(ob.solve(s))

入力

s = "mad"

出力

2

  1. 指定された文字列が母音回文であるかどうかを確認するPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −文字列（母音と子音の両方の文字を含む）が与えられ、すべての子音を削除してから、結果の文字列が回文であるかどうかを確認します。 ここでは、最初に文字列に存在するすべての子音を削除します。各値を1から計算された最小値まで除算することによって計算されて除数を計算するループ 条件が真であると評価されるたびに、カウンターは1ずつ増加します。 文字列内のすべての子音を削除します。ここで、母音の文字列が回文であるかどうか、つまり、指定された文字列とその反転が同一であるかどうかを確認します。それがpalindromep

  2. 文字列にすべての一意の文字が含まれているかどうかを確認するPythonプログラム

    この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。 問題の説明 sring入力が与えられた場合、文字列にすべての一意の文字が含まれているかどうかを確認する必要があります。 アプローチ ブール値の配列を作成します。ここで、インデックスiの変数フラグは、アルファベットの文字iが文字列に含まれているかどうかを示します。 この文字に2回目に遭遇したとき、文字列文字は一意ではなくなったため、すぐにfalseを返すことができます。 文字列の長さがアルファベットに表示される一意の文字数の値を超える場合も、falseを返すことができます。 文