题解 | #拼接所有的字符串产生字典序最小的字符串#

思路

我们知道string类型是重载了比较符的，所以可以直接用比较符进行比较，比较规则就是按字典序。
因此我们只需要调用sort函数重载cmp函数指定比较规则即可

方法一：sort重载cmp函数

cmp函数中要规定两字符串的比较规则是：

• s1 + s2 < s2 + s1
  保证这样的字典序才可以，最终将排序后的字符串组连接起来即可

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
    static bool cmp(const string& a, const string& b) {    // 重载cmp函数，将比较规则置入cmp
        return a+b < b+a;
    }

    string minString(vector<string>& strs) {
        // write code here
        sort(strs.begin(),strs.end(),cmp);                 // 按照新的规则重新排序给定字符串组
        string res = "";
        for(auto c : strs) {                               // 将排序后的字符串按序连接
            res += c;
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(nlogn)，sort函数的排序时间
• 空间复杂度：O(1)，没有借助其他空间

方法二：手写快速排序(超时不通过)

这个方法不借助sort函数，而是手写一个快速排序的方法，供大家复习快速排序用

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */

    static bool compare(const string& s1, const string& s2){        // 自定义比较
        return s1+s2 < s2+s1;            
    }

    int random_range(const int begin, const int end){               // 选择一个随机的pivot
        return random()%(end - begin) + begin;
    }

    int partition(vector<string>& strs, int low, int high,
                  bool (*cmp)(const string&, const string&)){
        int index = random_range(low, high);
        std::swap(strs[index], strs[high]);                          // 先将pivot元素挪到最高位置

        int small = -1;
        for(index=0; index<high; ++index){                           // 小于pivot的放左侧，大于pivot的放右侧
            if(cmp(strs[index], strs[high])){                        // 注意strs[index]和strs[high]都是string类型
                ++small;
                if(small != index)
                    std::swap(strs[small], strs[index]);
            }
        }
        ++small;
        std::swap(strs[small], strs[high]);                          // 将最终的位置交换回来
        return small;
    }

    void quick_sort_string(vector<string>& strs, int low, int high){  // 进行快速排序
        if(low < high){
            int middle = partition(strs, low, high, compare);         // 排好元素的对应位置
            quick_sort_string(strs, low, middle-1);                   // 递归左侧
            quick_sort_string(strs, middle+1, high);                  // 递归右侧
        }
    }                     
    string minString(vector<string>& strs) {
        // write code here
        int n = strs.size();
        assert((int)strs.size() == n && n >= 0);
        quick_sort_string(strs, 0, n-1);
        string res;
        for(int i=0; i<n; ++i)
            res += strs[i];
        return res;
    }
};

复杂度分析

• 时间复杂度：O(nlogn)，但是对于一些极端测试用例会达到O(n^2)
• 空间复杂度：O(logn)，考虑递归调用栈空间