Leetcode 1754. 构造字典序最大的合并字符串（DAY 130) ---- 贪心算法学习期

ゝ一世哀愁。 2022-10-17 13:37 110阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷TLE超时）
     *  代码实现(首刷自解 substr优化）

--------------------

## 原题题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷TLE超时） ##

class Solution { 
    public:
        string ret;
        void backtracking(string& temp,const string& word1,const string& word2,int pos1,int pos2)
        { 
            if(pos1 == word1.size() && pos2 == word2.size())
            { 
                ret = max(ret,temp);
                return;
            }
            string s;
            if(pos1 == word1.size() || word1[pos1] < word2[pos2] || word1[pos1] == word2[pos2])
            { 
                s = temp+word2[pos2];
                backtracking(s,word1,word2,pos1,pos2+1);
            }
            if(pos2 == word2.size() || word1[pos1] > word2[pos2] || word1[pos1] == word2[pos2])
            { 
                s = temp+word1[pos1];
                backtracking(s,word1,word2,pos1+1,pos2);
            }
        }
    
        string largestMerge(string word1, string word2) { 
            int pos1 = 0,pos2 = 0;
            string temp;
            backtracking(temp,word1,word2,0,0);
            return ret;
        }
    };

--------------------

## 代码实现(首刷自解 substr优化） ##

class Solution { 
    public:
    
        string largestMerge(string word1, string word2) { 
            int pos1 = 0,pos2 = 0;
            string ret;
            for(int i=0;i<word1.size()+word2.size();++i)
            { 
                if(pos1 == word1.size())  ret += word2[pos2++];
                else if(pos2 == word2.size())   ret += word1[pos1++];
                else
                { 
                    if(word1.substr(pos1) > word2.substr(pos2)) ret += word1[pos1++];
                    else    ret += word2[pos2++];
                }
            }
            return ret;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20221014/21361fc423f34805ab68b33fba107b5d.png