3_8最小辞書の順序付け
1678 ワード
指定された文字列配列の場合、すべての小さな文字列をつなぎ合わせる大きな文字列がすべての可能なつなぎ合わせの中で辞書の順序が最も小さいように、つなぎ合わせる順序を見つけます.
文字列配列strsを指定し、サイズを指定して、つなぎ合わせた列を返します.
テストサンプル:入力:[“abc”,“de”,2出力:“abcde”
文字列配列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