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

链接：1754.构造字典序最大的合并字符串
难度：Medium
标签：贪心、双指针、字符串
简介：返回你可以构造的字典序 最大 的合并字符串 merge 。

题解 1 - cpp

• 编辑时间：2022-12-24
• 执行用时：8ms
• 内存消耗：9.3MB
• 编程语言：cpp
• 解法介绍：后缀比较。

class Solution {
public:
    string largestMerge(string word1, string word2) {
        string ans = "";
        int i1 = 0, i2 = 0, n1 = word1.size(), n2 = word2.size();
        function<bool(int, int)> check = [&](int i1, int i2) -> bool {
            while (i1 < n1 && i2 < n2 && word1[i1] == word2[i2]) i1++, i2++;
            if (i2 == n2 && i1 == n1) return true;
            if (i2 == n2 && i1 != n1) return true;
            if (i2 != n2 && i1 == n1) return false;
            return word1[i1] > word2[i2];
        };
        while (i1 < n1 || i2 < n2) {
            if (i2 == n2 || word1[i1] > word2[i2]) ans += word1[i1++];
            else if (i1 == n1 || word1[i1] < word2[i2]) ans += word2[i2++];
            else {
                bool f = check(i1, i2);
                while (i1 < n1 && i2 < n2 && word1[i1] == word2[i2])
                    if (f) ans += word1[i1++];
                    else ans += word2[i2++];
            }
        }
        return ans;
    }
};