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

难度: Medium

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

Submission

运行时间: 61 ms

内存: 16.2 MB

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        
        merge = ""
        while word1 and word2:
            # 比较当前 word1 和 word2 哪个在字典序上更大，相等时需要比较后续字符
            if word1 > word2:
                # word1 字典序更大，选择 word1 的首字符
                merge += word1[0]
                word1 = word1[1:]
            else:
                # word2 字典序更大或相等，选择 word2 的首字符
                merge += word2[0]
                word2 = word2[1:]
        # 将非空字符串的剩余部分加到 merge 末尾
        merge += word1 + word2
        return merge

Explain

此题解的基本思路是贪心算法。在每一步中，比较两个字符串word1和word2的字典序。如果word1的字典序大于word2，或者在字典序相等的情况下，选择word1的首字符添加到结果字符串merge中；否则选择word2的首字符。这样的选择基于当前可见的信息，以确保每一步都能取得当前可能的最大字典序。当其中一个字符串为空时，将另一个非空字符串的剩余部分全部追加到merge中，得到最终结果。

时间复杂度: O((n+m)^2)

空间复杂度: O(n+m)

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        
        merge = ""
        while word1 and word2:
            # 比较当前 word1 和 word2 哪个在字典序上更大，相等时需要比较后续字符
            if word1 > word2:
                # word1 字典序更大，选择 word1 的首字符
                merge += word1[0]
                word1 = word1[1:]  # 移除word1的首字符
            else:
                # word2 字典序更大或相等，选择 word2 的首字符
                merge += word2[0]
                word2 = word2[1:]  # 移除word2的首字符
        # 将非空字符串的剩余部分加到 merge 末尾
        merge += word1 + word2
        return merge

Explore

在贪心算法中，如果当前比较的两个字符串的首字符相等，算法将考虑后续的所有字符来做决策。这意味着，如果word1和word2的首字符相同，算法不仅仅比较这一个字符，而是比较整个剩余的字符串。例如，如果word1和word2的首字符相同，那么接下来会比较剩余的word1[1:]和word2[1:]。这个过程会递归地继续，直到找到一个不相等的字符或者其中一个字符串结束。这种方法确保了每一步选择都是基于尽可能多的信息，从而使得最终合成的字符串具有最大的字典序。

当题解中提到的情况发生时，即其中一个字符串已经完全被使用（即为空），那么将另一个字符串的剩余部分直接加入到结果字符串merge中，是正确的做法。这是因为，当一个字符串为空时，另一个字符串的任何非空前缀都在字典序上大于空字符串。因此，直接将剩余的非空字符串加到合并字符串的末尾，不会导致字典序的降低，确保了结果字符串是最大的字典序。

在循环中比较word1和word2的字典序时，考虑的是全部剩余字符而不仅仅是首字符。在Python中，字符串比较是按照字典序进行的，比较操作会从两个字符串的开头开始，逐字符进行比较，直到找到一个不相等的字符或者一个字符串结束。这样的比较确保了每一步决策都是基于尽可能完整的信息，从而使得最终的合并字符串具有最大可能的字典序。