検索
ホームページバックエンド開発PHPチュートリアル循環インクリメントを使用して文字列をサブシーケンスにする

Make String a Subsequence Using Cyclic Increments

2825。循環インクリメントを使用して文字列をサブシーケンスにする

難易度:

トピック: 2 つのポインター、文字列

2 つの 0 インデックス付き 文字列 str1 と str2 が与えられます。

操作では、str1 のインデックスの セット を選択し、セット内のインデックス i ごとに、str1[i] を次の文字まで周期的にインクリメントします。つまり、「a」は「b」になり、「b」は「c」になり、同様に「z」は「a」になります。

操作 最大 1 回を実行することで str2 を str1 のサブシーケンスにできる場合は true を返し、それ以外の場合は falseを返します。

注: 文字列のサブシーケンスは、残りの文字の相対的な位置を乱すことなく、文字の一部 (おそらく何も削除しない) を削除することによって、元の文字列から形成される新しい文字列です。

例 1:

  • 入力: str1 = "abc"、str2 = "ad"
  • 出力: true
  • 説明: str1 のインデックス 2 を選択します。
    • str1[2] をインクリメントして 'd' にします。
    • したがって、str1 は "abd" になり、str2 はサブシーケンスになります。したがって、true が返されます。

例 2:

  • 入力: str1 = "zc"、str2 = "ad"
  • 出力: true
  • 説明: str1 のインデックス 0 と 1 を選択します。
    • str1[0] をインクリメントして 'a' にします。
    • str1[1] をインクリメントして「d」になります。
    • したがって、str1 は「ad」になり、str2 はサブシーケンスになります。したがって、true が返されます。

例 3:

  • 入力: str1 = "ab"、str2 = "d"
  • 出力: false
  • 説明: この例では、この操作を 1 回だけ使用して str2 を str1 のサブシーケンスにすることは不可能であることがわかります。
    • したがって、 false が返されます。

制約:

  • 1 5
  • 1 5
  • str1 と str2 は英小文字のみで構成されます。

ヒント:

  1. インクリメントするインデックスを個別に検討してください。
  2. 2 つのポインター (str1 のポインター i と str2 のポインター j) を、文字列の範囲内に確実に保持しながら維持できます。
  3. str1[i] と str2[j] の両方が一致する場合、または str1[i] のインクリメントが str2[j] と一致する場合、両方のポインターを増加します。それ以外の場合は、ポインター i のみをインクリメントします。
  4. j が str2 の末尾にある場合、一致するものが見つからなくなった後、str2 を str1 のサブシーケンスにすることができます。

解決策:

str1 の任意の文字に対して最大 1 つの循環インクリメント操作を実行することで、str2 を str1 のサブシーケンスにできるかどうかを確認する必要があります。

説明:

  • 2 つのポインターを使用します。i は str1 で、j は str2 です。
  • str1[i] の文字が str2[j] と一致する場合、両方のポインターを前方に移動します。
  • str1[i] を str2[j] と一致するように (周期的に) インクリメントできる場合は、それらを一致させてから両方のポインターを移動しようとします。
  • 上記の条件がどちらも当てはまらない場合は、str1 のポインタ i のみを移動します。
  • 最後に、str2 のすべての文字を一致させることができれば、str2 を str1 のサブシーケンスにすることができますが、それ以外の場合はできません。

このソリューションを PHP で実装してみましょう: 2825。循環インクリメントを使用して文字列をサブシーケンスにする

<?php /**
 * @param String $str1
 * @param String $str2
 * @return Boolean
 */
function canMakeSubsequence($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$str1 = "abc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "zc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "ab";
$str2 = "d";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false
?>

説明:

  1. 2 つのポインター: i と j は、それぞれ str1 と str2 の先頭に初期化されます。
  2. マッチング ロジック: ループ内で、str1[i] と str2[j] の文字が同じかどうか、または str2[j] と一致するように str1[i] を周期的にインクリメントできるかどうかをチェックします。
    • 循環インクリメント条件は、(ord($str1[$i]) 1 - ord('a')) % 26 を使用して処理され、str1[i] が str2[j] と一致するようにインクリメントできるかどうかをチェックします。
  3. サブシーケンス チェック: str2 を完全に反復処理した場合 (つまり、j == m)、str2 が str1 のサブシーケンスであることを意味します。それ以外の場合は、そうではありません。

時間計算量:

  • アルゴリズムは str1 を 1 回反復し、str2 の各文字は 1 回だけチェックされるため、時間計算量は O(n) になります。ここで、n は str1 の長さです。

空間の複雑さ:

  • 少数のポインターのみを使用し、入力サイズに応じて追加のスペースを必要としないため、スペースの複雑さは O(1) です。

このソリューションは、最大 1 回の循環インクリメント操作で str2 を str1 のサブシーケンスにできるかどうかを効率的にチェックします。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

  • LinkedIn
  • GitHub

以上が循環インクリメントを使用して文字列をサブシーケンスにするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
Laravelでフラッシュセッションデータを使用しますLaravelでフラッシュセッションデータを使用しますMar 12, 2025 pm 05:08 PM

Laravelは、直感的なフラッシュメソッドを使用して、一時的なセッションデータの処理を簡素化します。これは、アプリケーション内に簡単なメッセージ、アラート、または通知を表示するのに最適です。 データは、デフォルトで次の要求のためにのみ持続します。 $リクエスト -

PHPのカール:REST APIでPHPカール拡張機能を使用する方法PHPのカール:REST APIでPHPカール拡張機能を使用する方法Mar 14, 2025 am 11:42 AM

PHPクライアントURL(CURL)拡張機能は、開発者にとって強力なツールであり、リモートサーバーやREST APIとのシームレスな対話を可能にします。尊敬されるマルチプロトコルファイル転送ライブラリであるLibcurlを活用することにより、PHP Curlは効率的なexecuを促進します

Laravelテストでの簡略化されたHTTP応答のモッキングLaravelテストでの簡略化されたHTTP応答のモッキングMar 12, 2025 pm 05:09 PM

Laravelは簡潔なHTTP応答シミュレーション構文を提供し、HTTP相互作用テストを簡素化します。このアプローチは、テストシミュレーションをより直感的にしながら、コード冗長性を大幅に削減します。 基本的な実装は、さまざまな応答タイプのショートカットを提供します。 Illuminate \ support \ facades \ httpを使用します。 http :: fake([[ 'google.com' => 'hello world'、 'github.com' => ['foo' => 'bar']、 'forge.laravel.com' =>

ストレージを使用してLaravelでファイルのダウンロードを発見してください::ダウンロードストレージを使用してLaravelでファイルのダウンロードを発見してください::ダウンロードMar 06, 2025 am 02:22 AM

ストレージ:: Laravelフレームワークのダウンロード方法は、ファイルストレージの抽象化を管理しながら、ファイルのダウンロードを安全に処理するための簡潔なAPIを提供します。 サンプルコントローラーでストレージ::ダウンロード()を使用する例は次のとおりです。

Codecanyonで12の最高のPHPチャットスクリプトCodecanyonで12の最高のPHPチャットスクリプトMar 13, 2025 pm 12:08 PM

顧客の最も差し迫った問題にリアルタイムでインスタントソリューションを提供したいですか? ライブチャットを使用すると、顧客とのリアルタイムな会話を行い、すぐに問題を解決できます。それはあなたがあなたのカスタムにより速いサービスを提供することを可能にします

PHPにおける後期静的結合の概念を説明します。PHPにおける後期静的結合の概念を説明します。Mar 21, 2025 pm 01:33 PM

記事では、PHP 5.3で導入されたPHPの後期静的結合(LSB)について説明し、より柔軟な継承を求める静的メソッドコールのランタイム解像度を可能にします。 LSBの実用的なアプリケーションと潜在的なパフォーマ

PHPロギング:PHPログ分析のベストプラクティスPHPロギング:PHPログ分析のベストプラクティスMar 10, 2025 pm 02:32 PM

PHPロギングは、Webアプリケーションの監視とデバッグ、および重要なイベント、エラー、ランタイムの動作をキャプチャするために不可欠です。システムのパフォーマンスに関する貴重な洞察を提供し、問題の特定に役立ち、より速いトラブルシューティングをサポートします

Laravelサービスプロバイダーを登録および使用する方法Laravelサービスプロバイダーを登録および使用する方法Mar 07, 2025 am 01:18 AM

Laravelのサービスコンテナとサービスプロバイダーは、そのアーキテクチャの基本です。 この記事では、サービスコンテナ、詳細サービスプロバイダーの作成、登録、および実用的な使用法を例で説明します。 Oveから始めます

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。