3042。計算前綴和后綴對 I

難度：簡單

主題：數組、字符串、Trie、滾動哈希、字符串匹配、哈希函數

給你一個0索引字符串數組單詞。

讓我們定義一個 boolean 函數 isPrefixAndSuffix，它接受兩個字符串 str1 和 str2：

• 如果 str1 是 str2 的前綴¹和后綴²，則 isPrefixAndSuffix(str1, str2) 返回 true，否則返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 為 true，因為 "aba" 是 "ababa" 的前綴，也是后綴，但 isPrefixAndSuffix("abc", "abcd") 為 false。

返回一個整數，表示索引對 (i, j) 的 個數 ，使得 i

j，并且 isPrefixAndSuffix(words[i], Words[j]) 為 true。

示例1：

• 輸入：
words = ["a","aba","ababa","aa"]
• 輸出：
4
• 說明：
在此示例中，計數的索引對為： i = 0 且 j = 1，因為 isPrefixAndSuffix("a", "aba") 為 true。 i = 0 且 j = 2，因為 isPrefixAndSuffix("a", "ababa") 為 true。 i = 0 且 j = 3，因為 isPrefixAndSuffix("a", "aa") 為 true。 i = 1 且 j = 2，因為 isPrefixAndSuffix("aba", "ababa") 為 true。 因此，答案是4。

示例2：

• 輸入：
words = ["pa","papa","ma","mama"]
• 輸出：
2
• 說明：
在此示例中，計數的索引對為： i = 0 且 j = 1，因為 isPrefixAndSuffix("pa", "papa") 為 true。 i = 2 且 j = 3 因為 isPrefixAndSuffix("ma", "mama") 為 true。 因此，答案是2。

示例 3：

• 輸入：
words = ["abab","ab"]
• 輸出：
0
• 解釋：
在此示例中，唯一有效的索引對是 i = 0 和 j = 1，并且 isPrefixAndSuffix("abab", "ab") 為 false。 因此，答案是0。

約束：

1 1 words[i] 僅由小寫英文字母組成。

提示：

迭代所有索引對 (i, j)，使得 i 答案是 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):

   • 此函數循環(huán)遍歷所有可能的索引對 (i, j)，使得 i
   • 它調用isPrefixAndSuffix()來檢查words[i]是否既是words[j]的前綴又是后綴。
   • 如果條件為真，則會增加計數。

2. isPrefixAndSuffix($str1, $str2):

   • 此輔助函數檢查 str1 是否既是 str2 的前綴又是后綴。
   • 它使用 substr() 提取 str2 的前綴和后綴，并與 str1 進行比較。
   • 如果兩個條件都為 true，則返回 true，否則返回 false。

時間復雜度：

• 時間復雜度為O(n² x m)，其中n是單詞數組的長度，m是單詞數組的平均長度數組中的字符串。這是由于嵌套循環(huán)和 substr() 操作造成的。

示例輸出：

對于給定的輸入數組：

• [“a”，“aba”，“ababa”，“aa”]->輸出：4
• [“pa”，“papa”，“ma”，“mama”]->輸出：2
• [“abab”，“ab”]->輸出：0

該解決方案應該在給定的限制內有效地工作。

聯(lián)系鏈接

如果您發(fā)現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

---

1. 前綴 字符串的前綴是從字符串開頭開始延伸到字符串中任意點的子字符串。??

2. 后綴 字符串的后綴是從字符串中的任意點開始并延伸到其末尾的子字符串。??

以上是計算前綴和后綴對 I的詳細內容。更多信息請關注PHP中文網其他相關文章！