题目描述
这是 力扣上的 1768. 交替合并字符串,难度为 简单。
题目分析
题目的要求比较明确,通过我们查看给出的示例也能很清晰的认识到题目是需要从 word1 和 word2 中挨个拼接起来,最终得到一个拼接的结果
另外,给出的 word1 和 word2 并不一定是一样长的,若其中一个字符串中的字母使用完了,那么直接将另外一个字符串剩下的内容追加到结果串中即可
思考:
对于做算法新手来说,这个题是可以很好的应用到双指针的思想,并且可以落地到实践中
简单来说,这个题可以简单的遍历数组挨个拼接即可,但此处我们可以重点介绍一下什么叫做双指针:
双指针,见名知意,就是在我们实现算法的时候使用了两个指针,从这里也可以引申到三指针等等,此处指的指针,不一定在算法中真的是去使用指针来实现,也是使用的逻辑上的指针
一般咱们使用双指针,可能会用到序列,数组,链表上,这些数据结构咱们的双指针的展现形式可能是具体数据的索引位置,也可能是节点的地址
对于实现二叉树,多叉树的题目,或者是图类型的题目,那么这个双指针体现的方式就是指向对应的节点了,这里列一下可能会用到的场景:
- 一般那种追赶类型的题目,慢指针追赶快指针,成环类型的题目会用到
- 对于需要用滑动窗口,需要动态控制区间的题目可以使用到
- 当然,对于今天的字符串合并类型的题目可以用到,属于标记位置
- 还有很多,欢迎补充...
那么对于今天的题,简单逻辑如下:
- 定义 2 个变量i,j i, ji,j 用于分别遍历 word1和word2word1 和 word2word1和word2,并记录 word1word1word1 的字符长度为n nn,word2 word2word2 的为m mm
- 使用循环控制,进入循环的条件是$$ i
- 当能够进入循环的时候,说明此时 word1word1word1 和word2word2word2都没有遍历完毕,因此我们可以先追加 word1word1 word1对应的字符,再追加 word2word2 word2对应的字符
- 若从循环中退出,那么说明 word1word1word1 和 word2word2word2 其中一个必然是遍历完毕,我们通过 i,j,n,mi ,j ,n,m i,j,n,m的关系即可知道
- 最后将较长的一方的剩余字符串怼到结果上就行了
接下来,咱们就可以来实现编码了,咱们这次使用 golang 的方式来进行实现
Golang 的实现方式:
func mergeAlternately(word1, word2 string) string { // 定义双指针 i,j := 0,0 n,m := len(word1),len(word2) res := make([]byte, 0, n+m) // 遍历 word1 和 Word2 ,直到其中一个遍历完毕 for i<n && j<m { res = append(res, word1[i], word2[j]) i++ j++ } if i == n{ res = append(res, word2[j:]...) }else{ res = append(res, word1[i:]...) } return string(res) }
这种实现方式,咱们的时间复杂度为 O(n+m),咱们遍历了 word1 + word2,空间复杂度是 O(n+m),我们开辟了 res 结果字符串占用空间消耗
今天就到这里,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~