计算前缀和后缀对 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中文网其他相关文章！