sicily_1198 Substring

题目

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

Dr lee cuts a string S into N pieces,s[1],…,s[N].

Now, Dr lee gives you these N sub-strings: s[1],…s[N]. There might be several possibilities that the string S could be. For example, if Dr. lee gives you three sub-strings {“a”,“ab”,”ac”}, the string S could be “aabac”,”aacab”,”abaac”,…

Your task is to output the lexicographically smallest S.

Input

    The first line of the input is a positive integer T. T is the number of the test cases followed.

The first line of each test case is a positive integer N (1 <=N<= 8 ) which represents the number of sub-strings. After that, N lines followed. The i-th line is the i-th sub-string s[i]. Assume that the length of each sub-string is positive and less than 100.

Output

The output of each test is the lexicographically smallest S. No redundant spaces are needed.

Sample Input

1
3
a
ab
ac

Sample Output

aabac

思路

利用c++的比较操作符来判断两个字符串谁前谁后，笔者采用的是类似选择的算法，通过比较两个字符串顺序和逆序的和来判断是否要换位。
例如，"ac"+"ab" > "ab"+"ac", 换位，从而得出字典序。

代码

// 1198.cpp: http://soj.sysu.edu.cn/1198
// compare sub[i][j] and sub[j][i] to get the lexicographically smallest string
// Copyright (c) 2014 Junjie_Huang@SYSU(SNO:13331087). All Rights Reserved.
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

void subStringsSort(int N, string sub[8]) {
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (sub[i] + sub[j] > sub[j] + sub[i]) {
        string temp = sub[i];
        sub[i] = sub[j];
        sub[j] = temp;
      }
    }
  }
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    int N;
    string sub[8];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> sub[i];
    subStringsSort(N, sub);
    for (int i = 0; i < N; i++) cout << sub[i];
    cout << endl;
  }
  return 0;
}