LeetCode 1768. 交替合并字符串

约 4 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 LeetCode 75
标签
字符串 双指针

题目描述

✅ 1768. 交替合并字符串

image-20260928234313615

image-20260928234313616

题意分析

合并两个字符串时，从 word1 开始，轮流取一个字符追加到结果。两串内部的字符先后顺序都保持不变；当较短的字符串用完后，将较长字符串剩余的全部后缀按原顺序接到末尾。

每个输入字符必须使用一次，没有排序、去重或取舍。若两串长度分别为 m、n，最终长度一定为 m + n。

解法：按相同下标交替追加，再保留较长后缀

核心思路

[!blue]

在两串都还有字符的阶段，每一轮都会恰好从各自取出一个字符，因此两边已消耗的数量始终相同，可以共用一个下标 i，不需要分别维护两个进度。

只要 i < m 且 i < n，就先追加 word1[i]，再追加 word2[i]，然后将 i 加一。处理完一轮后，两串的前 i 个字符都已经按要求交替进入结果，而下标 i 仍指向各自第一个尚未使用的位置。

循环结束时，i 等于较短串的长度，至少一边已经用完。因此 [i, m) 和 [i, n) 至多有一个非空，把非空的一段整体追加即可，不必继续强行交替，也不会重复使用前面的字符。

Java 的 StringBuilder 和 Go 的 strings.Builder 负责顺序收集结果，按已知总长度预留容量可以减少扩容。题目限定小写英文字母，因此 Go 按字节下标读取和追加，与题目中的单个字符含义一致。

解题步骤

  1. 保存两串长度，为结果预留 m + n 的容量，令 i = 0。
  2. 两串都未结束时，依次追加当前下标的第一串字符和第二串字符，再推进 i。
  3. 如果第一串仍有剩余，追加 [i, m)；如果第二串仍有剩余，追加 [i, n)。
  4. 返回构造完成的字符串。

代码实现

class Solution {
    public String mergeAlternately(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // 答案长度恒为 m + n，预先把容量设满，底层数组一次分配到位，省掉扩容拷贝
        StringBuilder sb = new StringBuilder(m + n);
        int i = 0;

        // 交替段：两串都还有字符时，按「先 word1 后 word2」成对追加，循环体内无需越界判断
        while (i < m && i < n) {
            sb.append(word1.charAt(i));
            sb.append(word2.charAt(i));
            i++;
        }

        // 剩余段：此时 i == min(m, n)，两个条件至多命中一个，整段追加后缀
        if (i < m) {
            // 注意 append(CharSequence, start, end) 的第三个参数是结束下标，不是长度
            sb.append(word1, i, m);
        }

        if (i < n) {
            sb.append(word2, i, n);
        }

        return sb.toString();
    }
}

import (
    "strings"
)

func mergeAlternately(word1 string, word2 string) string {
    m, n := len(word1), len(word2)
    // 答案长度恒为 m + n，先 Grow 到位，避免 Builder 内部反复扩容拷贝
    var sb strings.Builder
    sb.Grow(m + n)
    i := 0
    // 交替段：两串都还有字符时，按「先 word1 后 word2」成对追加，循环体内无需越界判断
    for i < m && i < n {
        // 题目保证只含小写字母，均为单字节，按 byte 取用安全
        sb.WriteByte(word1[i])
        sb.WriteByte(word2[i])
        i++
    }
    // 剩余段：此时 i == min(m, n)，两个条件至多命中一个，整段追加后缀
    if i < m {
        sb.WriteString(word1[i:])
    }
    if i < n {
        sb.WriteString(word2[i:])
    }
    return sb.String()
}

复杂度分析

  • 时间复杂度：$O(m+n)$，每个输入字符恰好追加一次，最终输出也具有这个长度。
  • 空间复杂度：输出缓冲为 $O(m+n)$，除结果存储外只维护常量个长度与下标变量。

关键点总结

[!green]

  • 交替阶段两边进度同步，共用一个下标即可。
  • 每轮固定先第一串、后第二串，保留各自内部顺序。
  • 较短串结束后，只剩另一边的后缀需要一次追加。

易错点总结

[!yellow]

  • 先追加 word2，会颠倒题目规定的起始顺序。
  • 共同阶段使用逻辑或作为循环条件，会在较短串用完后继续访问它的下标。
  • 交替循环结束就返回，会漏掉较长串尚未使用的后缀。
  • 后缀从 i + 1 开始会漏掉第一个未使用字符，应从当前 i 开始。
  • Java 的 append(CharSequence, start, end) 最后一个参数是结束下标，不是要追加的长度。

相似题目

题目 难度 关联与区别
补充题 108. 交替合并两个链表 简单 同样交替合并并保留较长尾部，链表版本要先保存后继再改指针。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/49283099
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！