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

示例 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 仅由小写英文组成

class Solution {
public:
    string largestMerge(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size(), i = 0, j = 0;
        string ans;
        ans.reserve(n1+n2);
        while(i < n1 || j < n2)
        {
            if(i < n1 && j < n2 && word1[i] > word2[j])
                ans.push_back(word1[i++]);
            else if(i < n1 && j < n2 && word1[i] < word2[j])
                ans.push_back(word2[j++]);
            else if(i < n1 && j < n2 && word1[i] == word2[j])
            {   //相等的情况下，往后找到不相等的
                int k1 = i, k2 = j;
                while(k1 < n1 && k2 < n2 && word1[k1] == word2[k2])
                    k1++, k2++;
                if((k1 < n1 && k2 < n2 && word1[k1] > word2[k2]) || k2==n2)
                    ans.push_back(word1[i++]);
                else //if((k1 < n1 && k2 < n2 && word2[k2] > word1[k1]) || k1==n1)
                    ans.push_back(word2[j++]);
            }
            else if(i < n1 && j == n2)
                ans.push_back(word1[i++]);
            else
                ans.push_back(word2[j++]);
            // cout << i << " " << j << endl;
        }
        return ans;
    }
};