1768-交替合并字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你两个字符串 word1 和 word2 。请你从 word1
开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

示例 1：

**输入：** word1 = "abc", word2 = "pqr"
**输出：** "apbqcr"
**解释：** 字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：

**输入：** word1 = "ab", word2 = "pqrs"
**输出：** "apbqrs"
**解释：** 注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：

**输入：** word1 = "abcd", word2 = "pq"
**输出：** "apbqcd"
**解释：** 注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d

提示：

  • 1 <= word1.length, word2.length <= 100
  • word1 和 word2 由小写英文字母组成

方法一：双指针

思路与算法

我们直接按照题目的要求模拟即可。我们使用两个指针 i 和 j，初始时分别指向两个字符串的首个位置。随后的每次循环中，依次进行如下的两步操作：

  • 如果 i 没有超出 word}_1 的范围，就将 word}_1[i] 加入答案，并且将 i 移动一个位置；

  • 如果 j 没有超出 word}_2 的范围，就将 word}_2[j] 加入答案，并且将 j 移动一个位置。

当 i 和 j 都超出对应的范围后，结束循环并返回答案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        int i = 0, j = 0;
        
        string ans;
        ans.reserve(m + n);
        while (i < m || j < n) {
            if (i < m) {
                ans.push_back(word1[i]);
                ++i;
            }
            if (j < n) {
                ans.push_back(word2[j]);
                ++j;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String mergeAlternately(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int i = 0, j = 0;

        StringBuilder ans = new StringBuilder();
        while (i < m || j < n) {
            if (i < m) {
                ans.append(word1.charAt(i));
                ++i;
            }
            if (j < n) {
                ans.append(word2.charAt(j));
                ++j;
            }
        }
        return ans.toString();
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public string MergeAlternately(string word1, string word2) {
        int m = word1.Length, n = word2.Length;
        int i = 0, j = 0;

        StringBuilder ans = new StringBuilder();
        while (i < m || j < n) {
            if (i < m) {
                ans.Append(word1[i]);
                ++i;
            }
            if (j < n) {
                ans.Append(word2[j]);
                ++j;
            }
        }
        return ans.ToString();
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        m, n = len(word1), len(word2)
        i = j = 0

        ans = list()
        while i < m or j < n:
            if i < m:
                ans.append(word1[i])
                i += 1
            if j < n:
                ans.append(word2[j])
                j += 1
        
        return "".join(ans)
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var mergeAlternately = function(word1, word2) {
    const m = word1.length, n = word2.length;
    let i = 0, j = 0;

    const ans = [];
    while (i < m || j < n) {
        if (i < m) {
            ans.push(word1[i]);
            ++i;
        }
        if (j < n) {
            ans.push(word2[j]);
            ++j;
        }
    }
    return ans.join('');
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func mergeAlternately(word1, word2 string) string {
    n, m := len(word1), len(word2)
    ans := make([]byte, 0, n+m)
    for i := 0; i < n || i < m; i++ {
        if i < n {
            ans = append(ans, word1[i])
        }
        if i < m {
            ans = append(ans, word2[i])
        }
    }
    return string(ans)
}

复杂度分析

  • 时间复杂度：O(m+n)，其中 m 和 n 分别是字符串 word}_1 和 word}_2 的长度。

  • 空间复杂度：O(1) 或 O(m+n)。如果使用的语言支持可修改的字符串，那么空间复杂度为 O(1)，否则为 O(m+n)。注意这里不计入返回值需要的空间。

 Comments
On this page
1768-交替合并字符串