字符串—拼接最小字典序

https://github.com/yuanoOo/Algorithm/tree/master/String/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8B%BC%E6%8E%A5%E6%9C%80%E5%B0%8F%E5%AD%97%E5%85%B8%E5%BA%8F

拼接最小字典序

image.png

对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。
测试样例：
["abc","de"],2
"abcde"

算法步骤

• ①一般想法是，我们将每一个字符串按字典序进行排序即可，然后将这些字符串连接返回即可。但是这里有一个严重的bug。
• ②bug：例如"b","ba",如果按照一般的算法，我们会得到"bba",显然正确结果应为"bab".
• ③我们知道我们一开始的想法，即排序，是没有错的，我们只需要修正，以得出正确的比较结果。
• ④更正bug：为了比较两个字符串str1、str2，我们可以比较str1+str2和str2+str1。

Code

#include<iostream>
#include<string>
#include<vector>
using namespace std;

/*
 将一组字符串组合成一个"字典序最小"的字符串 
 1.quickSort +  (compare(str1+str2, str2+str1))
*/

class appendSmallDirSeq{
public:
    string findSmallest(vector<string> &strs)
    {
        int n = strs.size();
        //对vector<string>进行特殊的快速排序 
        quickSort(strs, 0, n - 1);
        
        string res;
        for(int i = 0; i < n; ++i)
            res += strs[i]; 
        
        return res;
    }
    
    //快速排序，以下均为快速排序代码 
    void quickSort(vector<string> &strs, int low, int high)
    {
        int q;
        if(low < high)
        {
            q = parition(strs, low, high);
            quickSort(strs, low, q-1);
            quickSort(strs, q+1, high);             
        }
    }
    
    int parition(vector<string> &strs, int low, int high)
    {
        string position = strs[high];
        int i = low - 1;
        
        for(int j = low; j < high; j++)
        {
            if(compare(strs[j], position))
            {
                ++i;
                swap(strs,j,i);
            }
        }
        
        //exchange a[i + 1] with posttion's index
        swap(strs, i + 1, high);
        return i+1;
    }
    
    int swap(vector<string> &strs, int low, int high)
    {
        string str(strs[low]);
        strs[low] = strs[high];
        strs[high] = str;
    }
    
    //本题正确的关键，正确比较符合本题的字符串大小 
    bool compare(string str1, string str2) 
    {
        string temp1 = str1 + str2;
        string temp2 = str2 + str1;
        
        if(temp1 <= temp2)
            return true;
        else
            return false;
    }
};

int main()
{
    string a("abc"),b("de"),c("cab");
    vector<string> vector;
    vector.push_back(a);
    vector.push_back(b);
    vector.push_back(c);
    
    appendSmallDirSeq append;
    string res = append.findSmallest(vector);
    cout<<res;
    return 0;
}