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

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

難易度: 簡単

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

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

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

• isPrefixAndSuffix(str1, str2) は、str1 が str2 のプレフィックス1 とサフィックス²の^両方である場合に 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(n² x m) です。ここで、n は単語配列の長さ、m は単語配列の平均長です。配列内の文字列。これは、ネストされたループと substr() 操作が原因です。

出力例:

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

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

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

連絡先リンク

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

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

• LinkedIn
• GitHub

---

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

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

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