【2022-12-24每日一题】1754. 构造字典序最大的合并字符串[Medium]
2022-12-24
2分钟阅读时长
2022-12-24每日一题：1754. 构造字典序最大的合并字符串
难度：Medium
标签：贪心 、 双指针 、 字符串
给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作：
- 如果
word1非空，将word1中的第一个字符附加到merge的末尾，并将其从word1中移除。<ul> <li>例如，<code>word1 = "abc" </code>且 <code>merge = "dv"</code> ，在执行此选项操作之后，<code>word1 = "bc"</code> ，同时 <code>merge = "dva"</code> 。</li> </ul> </li> <li>如果 <code>word2</code> 非空，将 <code>word2</code> 中的第一个字符附加到 <code>merge</code> 的末尾，并将其从 <code>word2</code> 中移除。 <ul> <li>例如，<code>word2 = "abc" </code>且 <code>merge = ""</code> ，在执行此选项操作之后，<code>word2 = "bc"</code> ，同时 <code>merge = "a"</code> 。</li> </ul> </li>
返回你可以构造的字典序 最大 的合并字符串 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仅由小写英文组成
方法一：贪心
// 写法一
func largestMerge(word1 string, word2 string) string {
m, n := len(word1), len(word2)
ans := make([]byte, 0, m + n)
for i, j := 0, 0; i < m || j < n; {
// 注意第二个条件，比较字符串的字典序
if i < m && word1[i:] > word2[j:] {
ans, i = append(ans, word1[i]), i+1
} else {
ans, j = append(ans, word2[j]), j+1
}
}
return string(ans)
}
// 写法二 使用strings.Builder
func largestMerge(word1 string, word2 string) string {
m, n, i, j:= len(word1), len(word2), 0, 0
var ans strings.Builder
for i < m && j < n {
// 注意第二个条件，比较字符串的字典序
if word1[i:] > word2[j:] {
ans.WriteByte(word1[i])
i++
} else {
ans.WriteByte(word2[j])
j++
}
}
ans.WriteString(word1[i:])
ans.WriteString(word2[j:])
return ans.String()
}
复杂度分析
时间复杂度：$O((m+n)×max(m,n))$，其中 m,n 分别表示两个字符串的长度。每次压入字符时需要进行后缀比较，每次两个字符串后缀比较的时间复杂度为 $O(max(m,n))$，一共最多需要比较 m+n 次，因此总的时间复杂度为 $O((m+n)×max(m,n))$。
空间复杂度：O(m+n)，其中 m,n 分别表示两个字符串的长度。每次比较时都会生成两个字符串的后缀，所需要的空间为 O(m+n)。