计算前缀和后缀对 I
Jan 09, 2025 am 06:08 AM3042。计算前缀和后缀对 I
难度:简单
主题:数组、字符串、Trie、滚动哈希、字符串匹配、哈希函数
给你一个0索引字符串数组单词。
让我们定义一个 boolean 函数 isPrefixAndSuffix,它接受两个字符串 str1 和 str2:
- 如果 str1 是 str2 的前缀1和后缀2,则 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 ?>
登录后复制
解释:
-
countPrefixAndSuffixPairs($words):
- 此函数循环遍历所有可能的索引对 (i, j),使得 i
- 它调用isPrefixAndSuffix()来检查words[i]是否既是words[j]的前缀又是后缀。
- 如果条件为真,则会增加计数。
-
isPrefixAndSuffix($str1, $str2):
- 此辅助函数检查 str1 是否既是 str2 的前缀又是后缀。
- 它使用 substr() 提取 str2 的前缀和后缀,并与 str1 进行比较。
- 如果两个条件都为 true,则返回 true,否则返回 false。
时间复杂度:
- 时间复杂度为O(n2 x m),其中n是单词数组的长度,m是单词数组的平均长度数组中的字符串。这是由于嵌套循环和 substr() 操作造成的。
示例输出:
对于给定的输入数组:
- [“a”,“aba”,“ababa”,“aa”]->输出:4
- [“pa”,“papa”,“ma”,“mama”]->输出:2
- [“abab”,“ab”]->输出:0
该解决方案应该在给定的限制内有效地工作。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
-
前缀 字符串的前缀是从字符串开头开始延伸到字符串中任意点的子字符串。 ↩
-
后缀 字符串的后缀是从字符串中的任意点开始并延伸到其末尾的子字符串。 ↩
以上是计算前缀和后缀对 I的详细内容。更多信息请关注PHP中文网其他相关文章!
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林
两个点博物馆:所有展览以及在哪里可以找到它们
3 周前
By 尊渡假赌尊渡假赌尊渡假赌

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林
两个点博物馆:所有展览以及在哪里可以找到它们
3 周前
By 尊渡假赌尊渡假赌尊渡假赌

热门文章标签

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)