ホームページ  >  記事  >  バックエンド開発  >  文字列を 3 つの部分文字列に分割できるかどうかを確認します。1 つの部分文字列は他の 2 つの部分文字列の部分文字列です。

文字列を 3 つの部分文字列に分割できるかどうかを確認します。1 つの部分文字列は他の 2 つの部分文字列の部分文字列です。

WBOY
WBOY転載
2023-09-22 11:53:16760ブラウズ

文字列を 3 つの部分文字列に分割できるかどうかを確認します。1 つの部分文字列は他の 2 つの部分文字列の部分文字列です。

この問題では、3 番目の部分文字列が最初の 2 つの部分文字列の部分文字列になるように、指定された文字列を分割する必要があります。

解決策を考えてみましょう。最初の 2 つの文字列に 3 番目の文字列のすべての文字が含まれている場合にのみ、3 番目の文字列を最初の 2 つの文字列の部分文字列にすることができます。したがって、指定された文字列内で頻度が 3 を超える文字を少なくとも 1 つ見つける必要があり、その 1 文字の 3 番目の部分文字列を取得できます。

問題文 - N 個の小文字のアルファベットを含む文字列 str が与えられています。部分文字列 c が a と b の部分文字列になるように、文字列を 3 つの部分文字列 a、b、c に分割できるかどうかを確認する必要があります。 3 つの部分文字列が見つかるかどうかに応じて、「はい」または「いいえ」を出力します。

###例### リーリー リーリー

イラスト

ここで、文字列を「tu」、「torialsPoin」、「t」に分割できます。したがって、3 番目の文字列は最初の 2 つの文字列の部分文字列になります。

リーリー リーリー

イラスト

どの文字の頻度も 3 を超えないため、指定された条件に基づいて文字列を 3 つの部分文字列に分割することはできません。

リーリー リーリー

イラスト

指定された条件によると、3 つの部分文字列

は 'h'、'h'、および 'hhahah' になります。 方法1

このメソッドでは、配列を使用して各文字の頻度を保存します。その後、頻度が 3 以上の文字を確認します。

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

ステップ 1
    - 長さ 26 の「freq」配列を定義します。
  • ステップ 2
  • - 文字列をループして、文字の頻度をカウントします。 for ループで、freq[str[i] – ‘a’] の値をインクリメントします。ここで、str[i] – ‘a’ は 0 ~ 26 のインデックスを与えます。
  • ステップ 3
  • - 次に、「freq」配列をループし、配列インデックスの値が「3」より大きい場合に true を返します。
  • ステップ 4
  • - ループが終了すると true を返します。
  • ステップ 5
  • - isSUbStringPossible() 関数の戻り値に基づいて、「はい」または「いいえ」を出力します。
  • ###例### リーリー ###出力### リーリー 時間計算量 - O(N)、文字列を反復処理する場合。

  • 定長配列を使用するため、空間計算量 - O(1)。

方法 2

このメソッドでは、まず文字列を文字配列に変換します。その後、 count() メソッドを使用して、配列内の特定の文字の頻度をカウントします。

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

ステップ 1

- サイズ「len 1」の配列を作成します。「len」は文字列の長さです。

ステップ 2
    - strcpy() メソッドを使用して、文字列を char 配列にコピーします。
  • ステップ 3
  • - for ループを合計 26 回繰り返します。
  • ステップ 4
  • - for ループで count() メソッドを使用して、特定の文字の出現数をカウントします。
  • count() メソッドは、最初の引数として開始位置への参照、2 番目の引数として終了位置への参照、そして 3 番目の引数として文字を受け取ります。

    ここでは、文字の ASCII 値をパラメータとして渡す必要があり、I ‘a’ を使用して値を取得します。
  • ステップ 5 - count() メソッドが 3 以上を返す場合は true を返します。

  • ステップ 6

    - ループが終了すると false を返します。
  • ###例### リーリー ###出力### リーリー 時間計算量 - count() メソッドが char 配列を反復して文字数をカウントするため、O(N)。また、strcpy() メソッドには O(N) 時間がかかります。

  • 文字列を文字配列に格納するため、空間複雑度 - O(N)。
  • ###結論は###

    文字列を 3 つの部分文字列に分割し、1 つの部分文字列が他の 2 つの部分文字列の部分文字列になるようにする 2 つの方法を学習しました。 2 番目の方法のコードは読みやすく、初心者にも優しいですが、時間とスペースがより高価になります。

以上が文字列を 3 つの部分文字列に分割できるかどうかを確認します。1 つの部分文字列は他の 2 つの部分文字列の部分文字列です。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。