1768. 交替合并字符串 详细题解

题目名称1768. 交替合并字符串题目来源LeetCode / 力扣题目难度简单题目链接https://leetcode.cn/problems/merge-strings-alternately/一、暴力解法最容易想到的方法思路说明采用单指针遍历的直观思路用一个索引变量从头开始遍历先取第一个字符串的字符再取第二个字符串的字符交替追加到结果中当索引超出其中一个字符串的长度后继续把另一个字符串剩余的字符全部追加到结果末尾。时间复杂度设word1长度为nword2长度为m需要遍历所有字符各一次时间复杂度为O(n m)。空间复杂度需要创建一个新字符串存储最终结果长度为nm额外空间复杂度为O(n m)这是存储结果的必要空间无法省略。适用场景适合所有场景逻辑直白、代码易写新手入门首选本题暴力法已经足够高效。C 代码实现cpp运行#include string using namespace std; class Solution { public: string mergeAlternately(string word1, string word2) { string res; // 存储最终结果 int i 0; // 单指针 int len1 word1.size(); int len2 word2.size(); // 交替取字符直到其中一个字符串遍历完 while (i len1 i len2) { res word1[i]; res word2[i]; i; } // 追加 word1 剩余字符 while (i len1) { res word1[i]; i; } // 追加 word2 剩余字符 while (i len2) { res word2[i]; i; } return res; } };二、优化解法时间 / 空间复杂度最优的方法思路演进暴力法的冗余用了 3 个循环代码稍显冗余改进方向用双指针替代单指针一个循环搞定所有逻辑代码更简洁效率完全一致本题特性必须遍历所有字符、必须存储结果没有可优化的计算冗余因此最优解法仅优化代码结构不改变复杂度。核心思想双指针分别遍历两个字符串交替追加字符任一字符串遍历完后直接拼接另一个字符串的剩余部分。算法步骤① 定义双指针i0遍历 word1、j0遍历 word2定义结果字符串② 循环只要i没遍历完word1或j没遍历完word2③ 如果i未越界追加word1[i]并i④ 如果j未越界追加word2[j]并j④ 循环结束返回结果。时间复杂度依旧是O(n m)和暴力法一致是理论最优时间复杂度必须访问所有字符。空间复杂度依旧是O(n m)存储结果的必要空间无法再优化因为题目要求返回新字符串必须开辟空间。C 代码实现关键注释cpp运行#include string using namespace std; class Solution { public: string mergeAlternately(string word1, string word2) { string res; int i 0, j 0; // 双指针i遍历word1j遍历word2 int len1 word1.size(), len2 word2.size(); // 一个循环完成交替拼接 剩余字符追加 while (i len1 || j len2) { // 先添加word1的当前字符如果有 if (i len1) { res word1[i]; } // 再添加word2的当前字符如果有 if (j len2) { res word2[j]; } } return res; } };三、两种解法对比总结解法时间复杂度空间复杂度优点缺点暴力法O(nm)O(nm)思路极度直观易理解循环数量多代码冗余最优解法O(nm)O(nm)代码简洁一个循环搞定无明显缺点完美四、进一步思考可选是否存在时间 O (n) 且空间 O (1) 的解法不存在。时间必须遍历所有字符复杂度为O(nm)题目要求返回新的合并字符串必须开辟空间存储结果空间无法做到 O (1)。如果输入数据规模扩大 10 倍哪种解法会先失效两种解法复杂度完全一致都不会失效效率相同。类似题目推荐88. 合并两个有序数组最长公共前缀反转字符串中的单词 III五、调试与验证1. 手动模拟示例示例 1word1abc, word2pqri0, j0添加a→p→ resapi1, j1添加b→q→ resapbqi2, j2添加c→r→ resapbqcr遍历完成返回结果。2. 边界测试用例空字符串word1, word2abc→ 输出abc单字符word1a, word2b → 输出 ab一长一短word1abcd, word2pq → 输出 apbqcd