ホームページ バックエンド開発 PHPチュートリアル プレフィックスとサフィックスのペアを数える I

プレフィックスとサフィックスのペアを数える I

Jan 09, 2025 am 06:08 AM

Count Prefix and Suffix Pairs I

3042。プレフィックスとサフィックスのペアを数える I

難易度: 簡単

トピック: 配列、文字列、トライ、ローリング ハッシュ、文字列マッチング、ハッシュ関数

インデックスが 0 の 文字列配列ワードが与えられます。

2 つの文字列 str1 と str2 を取る boolean 関数 isPrefixAndSuffix を定義しましょう。

  • isPrefixAndSuffix(str1, str2) は、str1 が str2 のプレフィックス1 とサフィックス2両方である場合に true を返し、それ以外の場合は false を返します。

たとえば、「aba」は「ababa」の接頭辞であり接尾辞でもあるため、isPrefixAndSuffix("aba", "ababa") は true ですが、isPrefixAndSuffix("abc", "abcd") は false です。

i 数 を表す整数を返します。 j、および isPrefixAndSuffix(words[i], Words[j]) は true です。

例 1:

  • 入力: 単語 = ["a","aba","ababa","aa"]
  • 出力: 4
  • 説明: この例では、カウントされるインデックスのペアは次のとおりです。 isPrefixAndSuffix("a", "aba") が true であるため、i = 0 および j = 1。 isPrefixAndSuffix("a", "ababa") が true であるため、i = 0 および j = 2。 isPrefixAndSuffix("a", "aa") が true であるため、i = 0 および j = 3。 isPrefixAndSuffix("aba", "ababa") が true であるため、i = 1 および j = 2 となります。 したがって、答えは 4.

例 2:

  • 入力: 単語 = ["pa","papa","ma","mama"]
  • 出力: 2
  • 説明: この例では、カウントされるインデックスのペアは次のとおりです。 isPrefixAndSuffix("pa", "papa") が true であるため、i = 0 および j = 1。 isPrefixAndSuffix("ma", "mama") が true であるため、i = 2 および j = 3。 したがって、答えは 2.

例 3:

  • 入力: 単語 = ["abab","ab"]
  • 出力: 0
  • 説明: この例では、唯一の有効なインデックス ペアは i = 0 および j = 1 であり、isPrefixAndSuffix("abab", "ab") は false です。 したがって、答えは0です。

制約:

  • 1
  • 1
  • Words[i] は英小文字のみで構成されています。

ヒント:

  1. i を確認します。
  2. 答えは、isPrefixAndSuffix(words[i], Words[j]) == true となるペアの合計数です。

解決策:

すべてのインデックス ペア (i, j) (i

このソリューションを PHP で実装してみましょう: 3042。プレフィックスとサフィックスのペアを数える I

<?php
/**
 * @param String[] $words
 * @return Integer
 */
function countPrefixAndSuffixPairs($words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to check if str1 is both a prefix and a suffix of str2
 *
 * @param $str1
 * @param $str2
 * @return bool
 */
function isPrefixAndSuffix($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$words1 = ["a", "aba", "ababa", "aa"];
$words2 = ["pa", "papa", "ma", "mama"];
$words3 = ["abab", "ab"];

echo countPrefixAndSuffixPairs($words1) . "\n";  // Output: 4
echo countPrefixAndSuffixPairs($words2) . "\n";  // Output: 2
echo countPrefixAndSuffixPairs($words3) . "\n";  // Output: 0
?>
ログイン後にコピー

説明:

  1. countPrefixAndSuffixPairs($words):

    • この関数は、i
    • isPrefixAndSuffix() を呼び出して、words[i] が Words[j] の接頭辞と接尾辞の両方であるかどうかを確認します。
    • 条件が true の場合、カウントが増加します。
  2. isPrefixAndSuffix($str1, $str2):

    • このヘルパー関数は、str1 が str2 のプレフィックスとサフィックスの両方であるかどうかをチェックします。
    • substr() を使用して str2 のプレフィックスとサフィックスを抽出し、str1 と比較します。
    • 両方の条件が true の場合は true を返し、それ以外の場合は false を返します。

時間計算量:

  • 時間計算量は O(n2 x m) です。ここで、n は単語配列の長さ、m は単語配列の平均長です。配列内の文字列。これは、ネストされたループと substr() 操作が原因です。

出力例:

指定された入力配列の場合:

  • ["a", "aba", "ababa", "aa"] ->出力: 4
  • [「パ」、「パパ」、「マ」、「ママ」] ->出力: 2
  • ["アバブ"、"アブ"] ->出力: 0

このソリューションは、指定された制約内で効率的に機能するはずです。

連絡先リンク

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

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

  • LinkedIn
  • GitHub

  1. Prefix 文字列の接頭辞は、文字列の先頭から始まり、文字列内の任意の点まで続く部分文字列です。 ↩

  2. サフィックス 文字列のサフィックスは、文字列内の任意の位置から始まり、その末尾まで続く部分文字列です。 ↩

以上がプレフィックスとサフィックスのペアを数える Iの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットな記事タグ

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

11ベストPHP URLショートナースクリプト(無料およびプレミアム) 11ベストPHP URLショートナースクリプト(無料およびプレミアム) Mar 03, 2025 am 10:49 AM

11ベストPHP URLショートナースクリプト(無料およびプレミアム)

Laravelでフラッシュセッションデータを使用します Laravelでフラッシュセッションデータを使用します Mar 12, 2025 pm 05:08 PM

Laravelでフラッシュセッションデータを使用します

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

Laravelテストでの簡略化されたHTTP応答のモッキング

LaravelのバックエンドでReactアプリを構築する:パート2、React LaravelのバックエンドでReactアプリを構築する:パート2、React Mar 04, 2025 am 09:33 AM

LaravelのバックエンドでReactアプリを構築する:パート2、React

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

PHPのカール:REST APIでPHPカール拡張機能を使用する方法

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

Codecanyonで12の最高のPHPチャットスクリプト

Instagram APIの紹介 Instagram APIの紹介 Mar 02, 2025 am 09:32 AM

Instagram APIの紹介

Laravelの通知 Laravelの通知 Mar 04, 2025 am 09:22 AM

Laravelの通知

See all articles