摘要

1754. 构造字典序最大的合并字符串

一 贪心算法分析

题目要求合并两个字符串 word1 与 word2，且要求合并后的字符串字典序最大。首先需要观察一下合并的选择规律，假设当前需要从 word1​ 的第 i 个字符和 word2​ 的第 j个字符选择一个字符加入到新字符串 merge 中，需要进行分类讨论:

• 如果 word1[i]>word2[j]，此时我们的最优选择是移除 word1[i]加入到 merge 中，从而保证 merge 的字典序最大；

• 如果 word1[i]<word2[j]，此时我们的最优选择是移除 word2[j] 加入到 merge，从而保证 merge 的字典序最大；

• 如果 word1[i]=word2[j]，此时则需要进一步讨论，结论如下：

  • 如果 word1 从i开始的后缀字典序大于 word2 从 j 开始的后缀，则此时优先选择移除 word1[i]加入到 merge 中；
  • 如果 word1 从 i 开始的后缀字典序小于 word2 从 j 开始的后缀，则此时优先选择移除 word2[j] 加入到 merge中；
  • 如果 word1从 i开始的后缀字典序等于 word2从 j开始的后缀，则此时任选一个均可；

当两个字符相等时，则我们最优选择为后缀较大的字符串，分类讨论如下：
-假设 word1[i]=word2[j]，此时两个字符串分别从 i,j开始还有 l 个字符相等，则此时word1[i+k]=word2[j+k],k∈[0,l−1]第 l+1 个字符时二者不相等，即满足 word1[i+l]≠word2[j+l]，我们可以假设 word1[i+l]<word2[j+l]。

-我们可以得到结论每次选择字典序较大的后缀进行移除一定可以保证得到最优的结果，其余的选择方法不一定能够保证得到最优结果。

1.2 复杂度分析

• 时间复杂度：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)。

1.3 code示例分析

/*** @description 利用的是双执行的来执行* @param: word1* @param: word2* @date: 2022/12/24 12:11* @return: java.lang.String* @author: xjl
*/
public String largestMerge(String word1, String word2) {if (word1==""){return word2;}else if (word2==""){return word1;}else {StringBuilder merge = new StringBuilder();int i = 0, j = 0;while (i < word1.length() || j < word2.length()) {if (i < word1.length() && word1.substring(i).compareTo(word2.substring(j)) > 0) {merge.append(word1.charAt(i));i++;} else {merge.append(word2.charAt(j));j++;}}return merge.toString();}
}

博文参考