题目

给你两个字符串 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 <= 3000
• word1 和 word2 仅由小写英文组成

标签: 贪心 双指针 字符串

思路

从word1和word2中一个个字符进行对比，大的字符则放入merge中。有种特殊情况，还需要根据字典大小排序，也就是说如果大家此时都为4个字符，最后个字符是word1大，则需要先取word1先，这里我们可以根据字典大小排序即可。

代码

    class Solution {
        public String largestMerge(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            StringBuilder builder = new StringBuilder(len1 + len2);
            int i = 0;
            int j = 0;
            // 遍历
            while (i < len1 && j < len2) {
                String value1 = word1.substring(i);
                String value2 = word2.substring(j);
                if (value1.compareTo(value2) > 0) {
                    builder.append(word1.charAt(i));
                    i++;
                } else {
                    builder.append(word2.charAt(j));
                    j++;
                }
            }
            // 遍历完后还有剩下
            if (i != len1 && j == len2) {
                builder.append(word1, i, len1);
            } else if (i == len1 && j != len2) {
                builder.append(word2, j, len2);
            }
            return builder.toString();
        }

    }

链接

• leetcode/算法/1754. 构造字典序最大的合并字符串