指定された文字列を回文にするために削除する必要がある最小の部分文字列

PHPz
リリース: 2023-08-30 17:49:03
転載
1336 人が閲覧しました

指定された文字列を回文にするために削除する必要がある最小の部分文字列

回文は、順方向と逆方向の両方で同じように読める一連の文字です。コンピューター サイエンスとプログラミングでは、回文は文字列操作の問題の一般的なテーマです。この記事では、回文にするために特定の文字列から削除する必要がある最小サイズの部分文字列を見つける方法を検討します。適切に構造化された C ソリューションを提供し、テスト ケースを示す例も含めます。

###問題文###

長さ 'n' の文字列 's' が与えられた場合、残りの文字列が回文になるように削除する必要がある部分文字列の最小サイズを見つける必要があります。

###アルゴリズム###

文字列「s」をパラメータとして受け取り、回文の場合は true を返し、それ以外の場合は false を返す isPalindrome という関数を作成します。

  • 文字列「s」をパラメータとして受け取る minSizeSubstringToRemove という関数を作成します。

  • 変数 'minSize' を文字列の長さに初期化します。

  • ループを使用して文字列を反復処理し、インデックス 'i' を 0 から 'n' まで増分します。

  • 各反復で、次の手順を実行します。-

  • 文字列の先頭からインデックス 'i' までの部分文字列を 2 つ作成し、インデックス 'i' から文字列の終わりまでの部分文字列を 1 つ作成します。
    • 部分文字列のいずれかが回文であるかどうかを確認します。

    • 部分文字列が回文である場合は、「minSize」を非回文部分文字列の長さと「minSize」の間の最小値に更新します。

    • 結果として「minSize」を返します。
  • ###例### リーリー ###出力### リーリー

    テストケースの例

  • 次の文字列を考えてみましょう: "abccbaab"。考えられる部分文字列とそれに対応する回文状態は次のとおりです:

左の部分文字列 = ""、右の部分文字列 = "abccbaab"、回文 = false

左の部分文字列 = "a"、右の部分文字列 = "bccbaab"、回文 = false

  • 左の部分文字列 = "ab"、右の部分文字列 = "ccbaab"、回文 = false

  • 左の部分文字列 = "abc"、右の部分文字列 = "cbaab"、回文 = false

  • 左の部分文字列 = "abcc"、右の部分文字列 = "baab"、回文 = false

  • 左の部分文字列 = "abccb"、右の部分文字列 = "aab"、回文 = true (左の部分文字列)

  • 左の部分文字列 = "abccba"、右の部分文字列 = "ab"、回文 = true (左の部分文字列)

  • 左の部分文字列 = "abccbaa"、右の部分文字列 = "b"、回文 = false

  • 左の部分文字列 = "abccbaab"、右の部分文字列 = ""、回文 = false

  • 上記の繰り返しから、削除する部分文字列の最小サイズは 2 であることがわかります。これは、左側の部分文字列が「abccba」で、右側の部分文字列が「ab」の場合に発生します。この場合、右側の部分文字列「ab」を削除すると、残りの文字列「abccba」が回文になります。

    ###結論は###
  • この記事では、特定の文字列を回文にするために削除する必要がある最小サイズの部分文字列を見つける問題を検討します。シンプルなループを利用して文字列を反復処理し、部分文字列を作成し、その回文ステータスをチェックして削除する必要がある部分文字列の最小サイズを見つける、明確で効率的な C 実装を提供します。
  • このアルゴリズムを理解することで、同様の概念をコンピューター サイエンスやプログラミングにおける他の文字列操作や回文問題の解決に適用できます。

以上が指定された文字列を回文にするために削除する必要がある最小の部分文字列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:tutorialspoint.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート