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

對于一個給定的字符串?dāng)?shù)組，請找到一種拼接順序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
給定一個字符串?dāng)?shù)組strs，同時給定它的大小，請返回拼接成的串。
測試樣例：
["abc","de"],2
"abcde"

算法步驟

• ①一般想法是，我們將每一個字符串按字典序進(jìn)行排序即可，然后將這些字符串連接返回即可。但是這里有一個嚴(yán)重的bug。
• ②bug：例如"b","ba",如果按照一般的算法，我們會得到"bba",顯然正確結(jié)果應(yīng)為"bab".
• ③我們知道我們一開始的想法，即排序，是沒有錯的，我們只需要修正，以得出正確的比較結(jié)果。
• ④更正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>進(jìn)行特殊的快速排序 
        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;
    }
    
    //本題正確的關(guān)鍵，正確比較符合本題的字符串大小 
    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;
}