算法随笔_37: 交替合并字符串
上一篇:算法随笔_36: 复写零-CSDN博客
=====
题目描述如下:
给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
返回 合并后的字符串 。
示例 1：
输入：word1 = "abc", word2 = "pqr" 输出："apbqcr" 解释：字符串合并情况如下所示： word1： a b c word2： p q r 合并后： a p b q c r
=====
算法思路:
题目要求交替添加字母。我们可以用双指针模拟合并字符串的过程。
设p1，p2两个指针，初始值分别指向两个字符串的起始元素。通过在两个字符串之间交替进行枚举访问元素，然后放入新的字符串中。最后把没有枚举完成的字符串合并到新字符串的末尾。
算法时间复杂度为O(m+n) 。m，n分别为两个字符串的长度。下面是代码实现:
class Solution(object):
def mergeAlternately(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: str
"""
res=[]
w1_len=len(word1)
w2_len=len(word2)
p1=0
p2=0
while p1<w1_len or p2<w2_len:
if p1<w1_len:
res.append(word1[p1])
p1+=1
if p2<w2_len:
res.append(word2[p2])
p2+=1
return "".join(res)