sicily1198. Substring

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

Problem Source

ZSUACM Team Member

 

题目分析：一次冒泡排序就行了， if str1 + str2 > str2 + str1 then swap(str1, str2) end if

 

代码参考：

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

int main()
{
    int t;
    cin >> t;
    while (t --)
    {
          int num;
          cin >> num;
          string s[num];
          for (int i = 0; i < num; ++ i)
          {
              cin >> s[i];
          }
          bool ch = true;
          for (int i = 0; i < num && ch == true; ++ i)
          {
              ch = false;
              for (int j = 1; j < num - i; ++ j)
              {
                  if (s[j - 1] + s[j] > s[j] + s[j - 1])
                  {
                      string temp = s[j - 1];
                      s[j - 1] = s[j];
                      s[j] = temp;
                      ch = true;
                  }
              }
          }
          for (int i = 0; i < num; ++ i)
          {
              cout << s[i];
          }
          cout << endl;
    }
}