指定された文内で部分文字列 S2 が出現した後に部分文字列 S1 が出現するかどうかを確認します。

王林
リリース: 2023-08-26 11:13:13
転載
548 人が閲覧しました

指定された文内で部分文字列 S2 が出現した後に部分文字列 S1 が出現するかどうかを確認します。

この問題では、指定された文字列 S 内で部分文字列 S2 が出現した後に部分文字列 S1 が出現するかどうかを確認する必要があります。この問題は、文字列 S 内の S1 と S2 の開始インデックスを比較することで解決できます。 p>

問題ステートメント - S、S1、S2 という名前の 3 つの部分文字列が与えられています。文字列 S には常に部分文字列として S1 が含まれます。指定された文字列 S の部分文字列 S2 の後に部分文字列 S1 が出現するかどうかを確認する必要があります。

###例

Enter – S = "abxtutorialspointwelcomepoint"、S1 = "ようこそ"、S2 = "ポイント";

出力 – はい

説明 – 文字列 S では、「ポイント」部分文字列が 2 回現れます。 1 つは「ようこそ」の前、もう 1 つは「ようこそ」の後です。したがって、文字列 S1 は文字列 S2 が発生した後に発生すると言えます。

入力– S = "abcdefgh"、S1 = "abcd"、S2 = "gh";

出力 – いいえ

説明S1 は文字列 S の先頭にあります。したがって、S1 は部分文字列 S2 の後には現れません。

入力– S = "abce"、S1 = "bc"、S2 = "xy";

出力 – いいえ

説明 – 文字列 S2 は文字列 S に存在しないため、No を出力します。

方法1

このアプローチでは、S2 部分文字列のすべての開始インデックスを検索し、コレクションに保存します。その後、S1 の開始インデックスを取得します。 S2 の各開始インデックスと S1 の開始インデックスを比較し、セット内のいずれかの値が S2 の開始インデックスより小さいことが判明した場合、部分文字列 S1 は部分文字列 S2 の出現後に発生すると言えます。

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

部分文字列 S2 の開始インデックスを格納するコレクションを定義します。
  • find() メソッドを使用して、S2 部分文字列の最初の開始インデックスを検索します。
  • while ループを使用して部分文字列 S2 のすべての開始インデックスを取得し、insert() メソッドを使用してそれらをコレクションに格納します。
  • 設定値を調べます。いずれかの値が、指定された文字列 S 内の部分文字列 S1 の開始インデックスより小さい場合、true を返します。
  • 最終的には false を返します。
  • ###例### リーリー ###出力### リーリー

    時間計算量 - O(N*K)。文字列 S2 の開始インデックスを見つける必要があるためです。
文字列 S2 の開始インデックスを保存するため、空間複雑度 - O(N)。

方法 2

このメソッドでは、文字列を反復処理します。文字列 S には常に文字列 S1 が含まれるため、S2 が S1 より前に発生することが判明した場合は true を返します。

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

変数の長さを格納するために、len、n1、および n2 変数を定義します。

文字列のトラバースを開始します。

  • 'temp 文字列を定義し、i 番目のインデックスから始まる長さ n2 の部分文字列で初期化します。

  • temp == S2 の場合、true を返します。

  • i 番目のインデックスから始まる長さ n1 の部分文字列を取得します。 temp == s1 の場合、false を返します。

  • 最終的に true を返します。

  • ###例### リーリー ###出力### リーリー
  • 時間計算量 – O(N*min(n1, n2))。長さ n1 と n2 の部分文字列が見つかるためです。

    部分文字列を格納するため、空間複雑度 - O(min(n1, n2)。
  • 最初のメソッドでは、コレクションを使用して S2 の開始インデックスを保存します。これには 2 番目のメソッドのコードよりも多くのスペースが必要です。 2 番目のメソッドのコードは、最初のメソッドよりも読みやすくなっています。あるいは、プログラマは、部分文字列 S2 が S1 の出現後に出現するかどうかをチェックする問題の解決を試みることもできます。

以上が指定された文内で部分文字列 S2 が出現した後に部分文字列 S1 が出現するかどうかを確認します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

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