首页 > 试题广场 >

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

[编程题]拼接所有的字符串产生字典序最小的字符串
  • 热度指数: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

备注:
时间复杂度,额外空间复杂度
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLEN 11

int comp(const void *a, const void *b);

int main(void) {
    int n;
    char **strs, *str, *res;
    scanf("%d", &n);
    strs = (char **) malloc(sizeof(char *) * n);
    for (int i = 0; i < n; i++) {
        str = (char *) malloc(MAXLEN);
        scanf("%s", str);
        strs[i] = str;
    }
    qsort(strs, n, sizeof(char *), comp);
    res = (char *) malloc((MAXLEN - 1) * n + 1);
    res[0] = '\0';
    for (int i = 0; i < n; i++) {
        strcat(res, strs[i]);
        free(strs[i]);
    }
    printf("%s\n", res);
    free(strs);
    free(res);
    return 0;
}

int comp(const void *a, const void *b) {
    char *s1, *s2;
    s1 = (char *) calloc(MAXLEN << 1, 1);
    s2 = (char *) calloc(MAXLEN << 1, 1);
    strcat(s1, *(char **) a);
    strcat(s1, *(char **) b);
    strcat(s2, *(char **) b);
    strcat(s2, *(char **) a);
    int ans = strcmp(s1, s2);
    free(s1);
    free(s2);
    return ans;
}

发表于 2022-02-11 17:45:35 回复(0)

问题信息

上传者:小小
难度:
1条回答 8666浏览

热门推荐

通过挑战的用户

查看代码