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 中的对应字符。例如，"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"
- 将剩余的 5 个 a 追加到 merge 的末尾。

示例 2：

输入：word1 = "abcabc", word2 = "abdcaba"
输出："abdcabcabcaba"

提示：

  • 1 <= word1.length, word2.length <= 3000
  • word1 和 word2 仅由小写英文字母组成。

解题思路

这是一个贪心算法问题。我们需要每次选择能构造出字典序最大字符串的字符。

基本思路

核心是每次都选择能让最终结果字典序最大的字符。有三种情况需要考虑：

  1. 当前字符不同：选择字典序更大的字符
  2. 当前字符相同：需要比较两个字符串的剩余部分
  3. 某个字符串已空：直接选择另一个字符串的字符

关键洞察

当两个字符串当前位置的字符相同时，我们需要比较两个字符串的后续部分。具体来说，我们应该选择"剩余子串字典序更大"的那个字符串。

最直观的做法是直接比较 word1[i:] 和 word2[j:]，哪个字典序更大就选择哪个。

算法流程

使用双指针 i 和 j 分别指向两个字符串的当前位置：

  1. 如果 word1[i] > word2[j]，选择 word1[i]
  2. 如果 word1[i] < word2[j]，选择 word2[j]
  3. 如果 word1[i] == word2[j]，比较 word1[i:] 和 word2[j:] 的字典序大小

时间复杂度为 O(n²)，其中 n 是两个字符串长度之和。虽然看起来不是最优，但对于题目给定的数据范围（3000）是完全可行的。

代码实现

class Solution {
public:
    string largestMerge(string word1, string word2) {
        string result;
        int i = 0, j = 0;
        
        while (i < word1.length() && j < word2.length()) {
            // 比较剩余的子串
            if (word1.substr(i) > word2.substr(j)) {
                result += word1[i++];
            } else {
                result += word2[j++];
            }
        }
        
        // 添加剩余字符
        while (i < word1.length()) {
            result += word1[i++];
        }
        
        while (j < word2.length()) {
            result += word2[j++];
        }
        
        return result;
    }
};

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        result = []
        i, j = 0, 0
        
        while i < len(word1) and j < len(word2):
            # 比较剩余的子串
            if word1[i:] > word2[j:]:
                result.append(word1[i])
                i += 1
            else:
                result.append(word2[j])
                j += 1
        
        # 添加剩余字符
        result.append(word1[i:])
        result.append(word2[j:])
        
        return ''.join(result)

public class Solution {
    public string LargestMerge(string word1, string word2) {
        StringBuilder result = new StringBuilder();
        int i = 0, j = 0;
        
        while (i < word1.Length && j < word2.Length) {
            // 比较剩余的子串
            if (string.Compare(word1.Substring(i), word2.Substring(j)) > 0) {
                result.Append(word1[i++]);
            } else {
                result.Append(word2[j++]);
            }
        }
        
        // 添加剩余字符
        while (i < word1.Length) {
            result.Append(word1[i++]);
        }
        
        while (j < word2.Length) {
            result.Append(word2[j++]);
        }
        
        return result.ToString();
    }
}

var largestMerge = function(word1, word2) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < word1.length && j < word2.length) {
        // 比较剩余的子串
        if (word1.substring(i) > word2.substring(j)) {
            result.push(word1[i++]);
        } else {
            result.push(word2[j++]);
        }
    }
    
    // 添加剩余字符
    while (i < word1.length) {
        result.push(word1[i++]);
    }
    
    while (j < word2.length) {
        result.push(word2[j++]);
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中 n = len(word1) + len(word2)。每次比较子串的时间复杂度为 O(n)，总共需要比较 n 次
空间复杂度O(n)，用于存储结果字符串和可能的子串操作临时空间

相关题目