3042。プレフィックスとサフィックスのペアを數(shù)える I

難易度: 簡(jiǎn)単

トピック: 配列、文字列、トライ、ローリング ハッシュ、文字列マッチング、ハッシュ関數(shù)

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

2 つの文字列 str1 と str2 を取る boolean 関數(shù) isPrefixAndSuffix を定義しましょう。

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

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

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

例 1:

• 入力: 単語(yǔ) = ["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:

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

例 3:

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

制約:

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

ヒント:

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

解決策:

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

このソリューションを PHP で実裝してみましょう: 3042。プレフィックスとサフィックスのペアを數(shù)える 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):

   • この関數(shù)は、i
   • isPrefixAndSuffix() を呼び出して、words[i] が Words[j] の接頭辭と接尾辭の両方であるかどうかを確認(rèn)します。
   • 條件が true の場(chǎng)合、カウントが増加します。

2. isPrefixAndSuffix($str1, $str2):

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

時(shí)間計(jì)算量:

• 時(shí)間計(jì)算量は O(n² x m) です。ここで、n は単語(yǔ)配列の長(zhǎng)さ、m は単語(yǔ)配列の平均長(zhǎng)です。配列內(nèi)の文字列。これは、ネストされたループと substr() 操作が原因です。

出力例:

指定された入力配列の場(chǎng)合:

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

このソリューションは、指定された制約內(nèi)で効率的に機(jī)能するはずです。

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

1. Prefix 文字列の接頭辭は、文字列の先頭から始まり、文字列內(nèi)の任意の點(diǎn)まで続く部分文字列です。??

2. サフィックス 文字列のサフィックスは、文字列內(nèi)の任意の位置から始まり、その末尾まで続く部分文字列です。??

以上がプレフィックスとサフィックスのペアを數(shù)える Iの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。