每日leetcode第0078天 1316. Distinct Echo Substrings

今天来做一道字符串的题目。

明确的回声字符串。回声字符串就是两个一样的字符串拼成的字符串。

我采用的是暴力解法和哈希集合的方式来做。

暴力解法有很多种方案,第一种是遍历所有i和j,判断从i到j是否为回声字符串。

这种情况把奇数的也都遍历进去了,不好。

第二种就是只遍历偶数的,这种遍历方式算是优化过了。

第三种就是遍历的i和j只跑一半,然后去后一段找是否回声。这个其实效率和上面差不多,就是写起来更巧妙。

第四种是只跑一半,并且完全思考清楚i和j跑的范围。

left1也就是i,我认为范围是0到len-1因为最后一个字母后面不可能还有东西和它形成回声了。

right1也就是j是有点绕的。它应该跑到从i到终点的一半,跑多了,后面的空间不够回声的长度。那么具体是多少呢。如果left1=0,那么我们计算一下就是(len – 1) / 2了,这个式子可以让奇数偶数都能用。那么left1变大后,这个范围跑动也就缩小了。变成了(len – left1 – 1) / 2 + left相当于还是剩下的一半或少一个的一半再加上left+1的右移。

使用substr来确定两个串是否回声,接下来。我们就再去哈希集合里面找,在不在里面,在就拉倒了,不在就要ans自增并把回声串放入哈希集合。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。