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

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

难度中等

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

双指针+使用Java的String.compareTo()方法

• 双指针指向两个字符串的第一个字符，如果两个指针指向的两个字符不同，选较大的那个字符
• 如果指针指向的两个字符相同，选后面的子字符串字典序较大的那个字符串的第一个字符

开始使用的前缀和，由于写的有bug没有通过，到最后没时间了，没调出来😭

class Solution {
    public String largestMerge(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        StringBuilder bd = new StringBuilder();
        int p1 = 0, p2 = 0;
        while (p1 < n1 || p2 < n2) {
            if (p1 < n1 && p2 < n2) {
                if (word1.charAt(p1) > word2.charAt(p2)) {
                    // 两个字符不同选较大的那个
                    bd.append(word1.charAt(p1));
                    p1++;
                } else if (word1.charAt(p1) < word2.charAt(p2)) {
                    bd.append(word2.charAt(p2));
                    p2++;
                } else {
                    // 两个字符相同，通过后边的子字符串的字典序决定选哪一个
                    if (word1.substring(p1, n1).compareTo(word2.substring(p2, n2)) > 0) {
                        // 字符串1的后面的子字符串的字典序大于字符串2的后面的子字符串的字典序
                        bd.append(word1.charAt(p1));
                        p1++;
                    } else {
                        // 
                        bd.append(word2.charAt(p2));
                        p2++;
                    }
                }
            } else if (p1 < n1) {
                bd.append(word1.charAt(p1));
                p1++;
            } else if (p2 < n2) {
                bd.append(word2.charAt(p2));
                p2++;
            }
        }
        return bd.toString();
    }
}

赏

谢谢你请我吃糖果

微信