2024-08-03:用 go 语言,给定一个从 0 开始的字符串数组 `words`, 我们定义一个名为 `isPrefixAndSuffix` 的布尔函数,该函数接受两个字符串参数 `str1` 和
2024-08-03:用 go 语言,给定一个从 0 开始的字符串数组 words
,
我们定义一个名为 isPrefixAndSuffix
的布尔函数,该函数接受两个字符串参数 str1
和 str2
。
当 str1
同时是 str2
的前缀和后缀时,函数返回 true
;否则返回 false
。
例如,isPrefixAndSuffix("aba", "ababa")
返回 true
,
因为 "aba" 既是 "ababa" 的前缀也是后缀,而 isPrefixAndSuffix("abc", "abcd")
返回 false
。
我们的目标是以整数形式返回符合条件的下标对 (i, j) 的数量,
其中满足 i < j
且 isPrefixAndSuffix(words[i], words[j])
为 true
。
输入: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 。
答案 2024-08-03:
题目来自 leetcode3045。
大体步骤如下:
1 定义函数 isPrefixAndSuffix(str1, str2)
:实现一个函数,判断 str1
是否是 str2
的前缀和后缀。
检查
str1
的长度是否大于str2
的长度。如果是,直接返回false
。确定
str2
的前缀是否与str1
相同。确定
str2
的后缀是否与str1
相同。如果上述两个条件都满足,返回
true
;否则返回false
。
2.遍历字符串数组 words
:
使用两个嵌套循环,外层循环设定为
i
,从 0 遍历到len(words)-1
,内层循环设定为j
,从i+1
遍历到len(words)-1
。这样可以确保i < j
。
3.调用 isPrefixAndSuffix
函数:在每对 (i, j)
中,调用 isPrefixAndSuffix(words[i], words[j])
。
如果函数返回
true
,则计数器增加 1。
4.返回计数器的值:最终,返回计数器的值,即为符合条件的下标对数量。
总时间复杂度
外层循环走
n
次,内层循环从i+1
到n
,最坏情况下为O(n)
。对于每一对
(i, j)
,调用isPrefixAndSuffix
需要在O(m)
时间内进行字符串的比较,其中m
是前缀或后缀的长度。因此,总的时间复杂度为
O(n^2 * m)
,其中m
是字符串的最长长度。
总额外空间复杂度
本算法使用少量的额外空间来存储计数器和函数的一些局部变量,因此额外空间复杂度为
O(1)
。函数内部的字符串比较不需要额外的存储,仅使用常量空间来存储临时变量,主存储体在输入
words
中。
综上所述,时间复杂度为 O(n^2 * m)
,额外空间复杂度为 O(1)
。
Go 完整代码如下:
Python 完整代码如下:
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/ed1dbaed1d906134ec7c3c636】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论