首页 > 试题广场 >

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

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

热度指数：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

备注:

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

算法知识视频讲解

helloxuanbao

#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)

Java

pein531

贪心算法，对字符串数组进行排序，如果某两个字符串a和b满足“a+b < b+a”，就将a排在b的前面，排序完后将字符串数组中的所有字符串连接起来就是要求的字典序最小的字符串。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strs = new String[n];
        for(int i = 0; i < n; i++) strs[i] = br.readLine();
        Arrays.sort(strs, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2) {
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) sb.append(strs[i]);
        System.out.println(sb.toString());
    }
}

发表于 2021-11-19 22:47:54 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

bool cmp(string a, string b){
    return a+b < b+a;
}

int main(){
    int n;
    cin>>n;
    string s[n];
    for(int i=0;i<n;i++)
        cin>>s[i];
    sort(s, s+n, cmp);
    for(int i=0;i<n;i++)
        cout<<s[i];
    return 0;
}

发表于 2020-05-15 00:43:51 回复(0)

XTher

#include <bits/stdc++.h>
using namespace std;
 
bool compare(string a, string b) {
	return (a + b) < (b + a);// 按照 str1+str2 ≤ str2+str1方式排序
}
string lowestString(vector<string> strs) {
	if (strs.empty()) {
		return  "";
	}
	sort(strs.begin(),strs.end(),compare);
	string res = "";
	for (int i = 0; i < strs.size(); ++i) {
		res += strs[i];
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	vector<string> str(n);
    for(int i= 0; i < n; i++) {
    	cin >> str[i];
	}
	cout << lowestString(str);
}

发表于 2020-02-23 11:17:02 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<string>str(n);
    for(int i=0;i<n;i++)
        cin>>str[i];
    sort(str.begin(),str.end(),[](string& a, string& b){return a + b < b + a;});
    for (int i = 0; i < n; ++i) 
        cout << str[i];
    return 0;
}

发表于 2019-09-24 20:50:19 回复(0)

牛客558934279号

python3代码如下：

from functools import cmp_to_key

n=int(input())
a=[]
for i in range(n):
a.append(input()) #输入
def comp(x,y):
if x+y<=y+x:
return -1
else:
return 1 #构建比较器
b=sorted(a,key=cmp_to_key(comp)) #两两比较贪心
print("".join(b))

发表于 2022-04-04 15:27:36 回复(0)

C++

致·爱丽丝

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n ;
    vector<string> vec;
    for (int i = 0; i < n; i ++) {
        string tmp;
        cin >> tmp;
        vec.push_back(tmp);
    }
    auto cmp  = [] (string s1,string s2) -> bool {
            int x =(s1 + s2) .compare(s2 + s1);  
            if (x < 1) return true;
            return false;
    };
    make_heap(vec.begin(),vec.end(),cmp);
    sort_heap(vec.begin(),vec.end(),cmp);
    for (auto x : vec) {
        cout << x;
    }
    return 0;
}

发表于 2022-07-16 19:22:14 回复(0)

Python 3

main_函数

from functools import cmp_to_key

def camp2(x,y):

if (x+y) < (y+x):

return -1

else:

return 1

n = input()

lst = []

for i in range(int(n)):

s = input()

lst.append(s)

print(''.join(sorted(lst,key = cmp_to_key(camp2))))

发表于 2022-03-03 20:22:23 回复(0)

不会飞的兔子

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] strs = new String[n];
        for(int i=0;i<n;i++){
            strs[i] = sc.next();
            //System.out.print(strs[i]);
        }
        System.out.println(lowestString(strs));
    }
    
    public static String lowestString(String strs[]){
        if(strs == null||strs.length == 0) return "";
        Arrays.sort(strs,new Mycomparator());
        StringBuilder res = new StringBuilder();
        for(int i=0;i<strs.length;i++){
            res.append(strs[i]);
        }
        return res.toString();
    }
}

class Mycomparator implements Comparator<String>{
    @Override
    public int compare(String a,String b){
        return (a+b).compareTo(b+a);
    }
}

发表于 2021-06-25 13:25:12 回复(0)

江山如画君

Go solution :

package main

import "fmt"
import "bytes"
import "sort"

//对 sarr 排序
func minDicOrder(sarr []string) []string {
	sort.Slice(sarr, func(i, j int) bool {
		return sarr[i]+sarr[j] < sarr[j]+sarr[i]
	})
	return sarr
}

//获得字符串总长度，以分配内存
func length(sarr []string) int {
	var sum int
	for _, str := range sarr {
		sum += len(str)
	}
	return sum
}

func main() {
    //输入输出
	var count int
	_, err := fmt.Scan(&count)
	if err != nil {
		panic(err)
	}

	sarr := make([]string, count)
	for i := 0; i < count; i++ {
		_, err := fmt.Scan(&sarr[i])
		if err != nil {
			panic(err)
		}
	}

	//切片排序
	orderArr := minDicOrder(sarr)

	//使用 bytes.Buffer, 防止字符串频繁分配造成的GC压力，
	var b bytes.Buffer
	//After Grow(n), at least n bytes can be written to the buffer without another allocation.
	b.Grow(length(sarr))

	for _, str := range orderArr {
		b.Write([]byte(str))
	}

	fmt.Println(b.String())
}

编辑于 2020-05-12 17:48:06 回复(0)

DejaVu、

import sys

number = int(sys.stdin.readline().strip())
result_list= []

while number>0:
lines = sys.stdin.readline().strip()
if len(lines) > 0:
result_list.append(lines)
number -= 1

for i in range (len(result_list)):
a = ''
for j in range (len(result_list[i])):
a += sorted(list(result_list[i]))[j]
result_list.pop(i)
result_list.insert(i,a)

b = ''
for k in range (len(result_list)):
b += result_list[k]
print(b)

各位大神，我这个结果对，但是为什么总超时啊，本人小白，请轻喷~

发表于 2020-04-28 04:20:01 回复(0)

包子冲汤胡辣汤

#include<cstdio>
(802)#include<iostream>
#include<string>
(765)#include<vector>
#include<algorithm>
using namespace std;
vector<string> v;
int cmp(string s1,string s2){
    return s1+s2<s2+s1;
}
int main(){
    int n;
    scanf("%d",&n);
    v.resize(n);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<n;++i){
        cout<<v[i];
    }
    return 0;
}

发表于 2020-04-09 19:02:55 回复(0)

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)