思路：

题目要求将所有的小字符串拼接成大字符串，使大字符串字典序最小，需要主要的有两点：

字符串越小的应该要在越靠前
字符串内部顺序不能动,只能添加连接

因此不是将所有较小的字符串排在前面相加，应该是s1+s2 < s2+s1比较，直接连接。比如：图片说明 方法一：冒泡排序法（超时） 数据量过大，严重超时，第一个案例就过不了。

class Solution {
public:
    string minString(vector<string>& strs) {
        string res = "";
        if(strs.size() == 0)
            return res; //优先处理特殊情况
        for(int i = 0; i < strs.size(); i++){
            bool flag = false;
            for(int j = 0; j < strs.size() - 1 - i; j++){
                if(strs[j + 1] + strs[j] < strs[j] + strs[j + 1]){
                    string temp = strs[j + 1];
                    strs[j + 1] = strs[j];
                    strs[j] = temp;
                    flag = true;
                }
                if(!flag)
                    break;
            }
        }
        for(int i = 0; i < strs.size(); i++){
            res += strs[i];
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，两层遍历
空间复杂度： $O (1)$ ，无额外空间

方法二：重载sort函数，使用快速排序 具体做法： 写一个静态函数，用于重载sort的比较部分。

class Solution {
public:
    static bool comp(string s1, string s2){ //若是放在class里，必须设置成static
        if(s1 + s2 < s2 + s1)   //改变运算法则，相加字典序更小放前面
            return true;
        else 
            return false;
    }
    string minString(vector<string>& strs) {
        string res = "";
        if(strs.size() == 0)
            return res; //优先处理特殊情况
        sort(strs.begin(), strs.end(), comp); //快排
        for(int i = 0; i < strs.size(); i++){ //连接字符串
            res += strs[i];
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，sort函数快速排序的复杂度
空间复杂度： $O (1)$ ，无额外空间使用

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

思路：