LeetCode 题解工作台
构造字典序最大的合并字符串
给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作： 如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。 例如， word1 …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们用指针 和 分别指向字符串 `word1` 和 `word2` 的第一个字符。然后循环，每次比较 和 的大小，如果 比 大，那么我们就将 加入答案，否则我们就将 加入答案。循环，直至 到达字符串 `word1` 的末尾，或者 到达字符串 `word2` 的末尾。 然后我们将剩余的字符串加入答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作：
- 如果
word1非空，将word1中的第一个字符附加到merge的末尾，并将其从word1中移除。- 例如，
word1 = "abc"且merge = "dv"，在执行此选项操作之后，word1 = "bc"，同时merge = "dva"。
- 例如，
- 如果
word2非空，将word2中的第一个字符附加到merge的末尾，并将其从word2中移除。- 例如，
word2 = "abc"且merge = ""，在执行此选项操作之后，word2 = "bc"，同时merge = "a"。
- 例如，
返回你可以构造的字典序 最大 的合并字符串 merge 。
长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字符串 b 更大。例如，"abcd" 按字典序比 "abcc" 更大，因为两个字符串出现不同的第一个位置是第四个字符，而 d 在字母表中的出现顺序位于 c 之后。
示例 1：
输入：word1 = "cabaa", word2 = "bcaaa" 输出："cbcabaaaaa" 解释：构造字典序最大的合并字符串，可行的一种方法如下所示： - 从 word1 中取第一个字符：merge = "c"，word1 = "abaa"，word2 = "bcaaa" - 从 word2 中取第一个字符：merge = "cb"，word1 = "abaa"，word2 = "caaa" - 从 word2 中取第一个字符：merge = "cbc"，word1 = "abaa"，word2 = "aaa" - 从 word1 中取第一个字符：merge = "cbca"，word1 = "baa"，word2 = "aaa" - 从 word1 中取第一个字符：merge = "cbcab"，word1 = "aa"，word2 = "aaa" - 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。
示例 2：
输入：word1 = "abcabc", word2 = "abdcaba" 输出："abdcabcabcaba"
提示：
1 <= word1.length, word2.length <= 3000word1和word2仅由小写英文组成
解题思路
方法一：贪心 + 双指针
我们用指针 和 分别指向字符串 word1 和 word2 的第一个字符。然后循环，每次比较 和 的大小，如果 比 大，那么我们就将 加入答案，否则我们就将 加入答案。循环，直至 到达字符串 word1 的末尾，或者 到达字符串 word2 的末尾。
然后我们将剩余的字符串加入答案即可。
时间复杂度 。其中 是字符串 word1 和 word2 的长度之和。
class Solution:
def largestMerge(self, word1: str, word2: str) -> str:
i = j = 0
ans = []
while i < len(word1) and j < len(word2):
if word1[i:] > word2[j:]:
ans.append(word1[i])
i += 1
else:
ans.append(word2[j])
j += 1
ans.append(word1[i:])
ans.append(word2[j:])
return "".join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m) if comparisons of remaining substrings are optimized, where n and m are the lengths of word1 and word2. Space complexity is O(n + m) for storing the merged string. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for two-pointer and greedy understanding.
- question_mark
Expect efficient lexicographical comparison without redundant scanning.
- question_mark
Check for correct handling when one string is exhausted before the other.
常见陷阱
外企场景- error
Naively concatenating characters without checking remaining substrings can fail on ties.
- error
Comparing only the first characters instead of full remaining substrings may produce a smaller merge.
- error
Forgetting to append the leftover of the non-empty string after the other is exhausted.
进阶变体
外企场景- arrow_right_alt
Return the lexicographically smallest merge instead of largest.
- arrow_right_alt
Merge more than two strings simultaneously using a generalized two-pointer greedy approach.
- arrow_right_alt
Apply the same merge logic with uppercase letters or custom lexicographical orders.