計算前綴和後綴對 I

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):

   • 此函數循環遍歷所有可能的索引對 (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是單字數組的平均長度數組中的字串。這是由於巢狀循環和 substr() 操作造成的。

範例輸出：

對於給定的輸入數組：

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

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

聯絡連結

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

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

• 領英
• GitHub

---

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

2. 後綴 字串的後綴是從字串中的任意點開始並延伸到其末尾的子字串。 ↩

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