3_8最小辞書の順序付け

1678 ワード

指定された文字列配列の場合、すべての小さな文字列をつなぎ合わせる大きな文字列がすべての可能なつなぎ合わせの中で辞書の順序が最も小さいように、つなぎ合わせる順序を見つけます.
文字列配列strsを指定し、サイズを指定して、つなぎ合わせた列を返します.
テストサンプル:入力:[“abc”,“de”,2出力:“abcde”
class Prior {
public:
    void swap_str(vector &strs, int i, int j)
    {
        string temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
    //  , A B ,  B 
    int cmp_str_joint(string A, string B)
    {
        return (A+B).compare(B+A);
    }

    // idx  , curr , end 
    void quick_sort_string(vector &strs, int start, int end)
    {
        int len = end - start + 1;
        if(1 >= len){
            return;
        }
        string curr = strs[start];
        int idx = start, p_end = end;
        for(int i=1; i0)  , 
            if(cmp_str_joint(curr, strs[idx+1])>0){
                strs[idx] = strs[idx+1];
                ++idx;
            }else{
                swap_str(strs, p_end, idx+1);
                --p_end;
            }
        }
        strs[idx] = curr;
        quick_sort_string(strs, start, idx-1);
        quick_sort_string(strs, idx+1, end);
    }
    string findSmallest(vector strs, int n) {
        // write code here
        quick_sort_string(strs, 0, n-1);
        string result;
        for(int i=0; i strs, int n) {
        // write code here
        sort(strs.begin(), strs.end(), my_cmp);
        string result;
        for(int i=0; i