Java编程实战21：构造字典序最大的合并字符串

目录 构造字典序最大的合并字符串题目示例 1示例 2提示 解答解题思路完整代码

构造字典序最大的合并字符串 题目

给你两个字符串 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 仅由小写英文组成 解答 解题思路

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

如果 word 1 [ i ] > word 2 [ j ] \textit{word}_1[i] > \textit{word}_2[j] word1​[i]>word2​[j]，此时我们的最优选择是移除 word 1 [ i ] \textit{word}_1[i] word1​[i] 加入到 merge \textit{merge} merge 中，从而保证 merge \textit{merge} merge 的字典序最大；如果 word 1 [ i ] < word 2 [ j ] \textit{word}_1[i] < \textit{word}_2[j] word1​[i]<word2​[j]，此时我们的最优选择是移除 word 2 [ j ] \textit{word}_2[j] word2​[j] 加入到 merge \textit{merge} merge，从而保证 merge \textit{merge} merge 的字典序最大；如果 word 1 [ i ] = word 2 [ j ] \textit{word}_1[i] = \textit{word}_2[j] word1​[i]=word2​[j]，此时则需要进一步讨论，结论如下： 如果 word 1 \textit{word}_1 word1​ 从 i i i 开始的后缀字典序大于 word 2 \textit{word}_2 word2​ 从 j j j 开始的后缀，则此时优先选择移除 word 1 [ i ] \textit{word}_1[i] word1​[i] 加入到 merge \textit{merge} merge 中；如果 word 1 \textit{word}_1 word1​ 从 i i i 开始的后缀字典序小于 word 2 \textit{word}_2 word2​ 从 j j j 开始的后缀，则此时优先选择移除 word 2 [ j ] \textit{word}_2[j] word2​[j] 加入到 merge \textit{merge} merge 中；如果 word 1 \textit{word}_1 word1​ 从 i i i 开始的后缀字典序等于 word 2 \textit{word}_2 word2​ 从 j j j 开始的后缀，则此时任选一个均可；

当两个字符相等时，则我们最优选择为后缀较大的字符串，分类讨论如下： 假设 word 1 [ i ] = word 2 [ j ] \textit{word}_1[i] = \textit{word}_2[j] word1​[i]=word2​[j]，此时两个字符串分别从 i , j i,j i,j 开始还有 l l l 个字符相等，则此时 word 1 [ i + k ] = word 2 [ j + k ] , k ∈ [ 0 , l − 1 ] \textit{word}_1[i+k] = \textit{word}_2[j+k], k \in [0,l-1] word1​[i+k]=word2​[j+k],k∈[0,l−1]，第 l + 1 l+1 l+1 个字符时二者不相等，即满足 word 1 [ i + l ] ≠ word 2 [ j + l ] \textit{word}_1[i + l] \neq \textit{word}_2[j + l] word1​[i+l]=word2​[j+l]，我们可以假设 word 1 [ i + l ] < word 2 [ j + l ] \textit{word}_1[i + l] < \textit{word}_2[j + l] word1​[i+l]<word2​[j+l]。 例如 word 1 = “bcadea" \textit{word}_1 = \text{``bcadea"} word1​=“bcadea" 与 word 2 = “_bcadf” \textit{word}_2 = \text{``\_bcadf''} word2​=“_bcadf”，此时 i = 0 , j = 1 , l = 4 i = 0, j = 1, l = 4 i=0,j=1,l=4。

完整代码 class Solution { public String largestMerge(String word1, String word2) { StringBuilder merge = new StringBuilder(); int i = 0, j = 0; while (i < word1.length() || j < word2.length()) { if (i < word1.length() && word1.substring(i) pareTo(word2.substring(j)) > 0) { merge.append(word1.charAt(i)); i++; } else { merge.append(word2.charAt(j)); j++; } } return merge.toString(); } }