算法随笔_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=0p2=0while p1<w1_len or p2<w2_len:if p1<w1_len:res.append(word1[p1])p1+=1if p2<w2_len:res.append(word2[p2])p2+=1return "".join(res)