拼接所有的字符串产生字典序最小的字符串

[编程题]拼接所有的字符串产生字典序最小的字符串

热度指数：2735 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串。

输入描述:

输入包含多行，第一行包含一个整数n，代表字符串数组strs的长度，后面n行，每行一个字符串，代表strs[i]（保证所有字符串长度都小于10）。

输出描述:

输出一行，包含一个字符串，代表返回的字典序最小的字符串。

示例1

输入

2
abc
de

输出

abcde

示例2

输入

2
b
ba

输出

bab

备注:

时间复杂度，额外空间复杂度。

算法知识视频讲解

Python

D201903260944941

import sys
import functools

n = int(input())
strs = list()

while n >= 0:
    l = sys.stdin.readline().strip()
    if l is not '':
        strs.append(l)
    n = n - 1

def custom_sort(x, y):
    if (x+y) < (y+x):
        return -1
    else:
        return 1
    return 0

strs = sorted(strs,key = functools.cmp_to_key(custom_sort))
print(''.join(strs))

编辑于 2020-04-01 15:21:58 回复(1)