首页 > 试题广场 >

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

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

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

给定一个长度为 n 的字符串数组 strs ，请找到一种拼接顺序，使得数组中所有的字符串拼接起来组成的字符串是所有拼接方案中字典序最小的，并返回这个拼接后的字符串。

数据范围： $1 \le n \le 1000000$ ， $1 \le len(strs_i)\le 10$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(nlognlen(strs_i))$

示例1

输入

["abc","de"]

输出

"abcde"

示例2

输入

["a","a","b"]

输出

"aab"

备注:

算法知识视频讲解

牛客670170875号

不知道为啥报错。。。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int cmp(const void *a ,const void*b){

return strcmp((char *)a, (char *)b);

}

char* minString(char** strs, int strsLen ) {

int i=0;

char *res={0};

res=(char *)malloc(strsLen*sizeof(strs[0]));

qsort(strs, strsLen, sizeof(strs[0]), cmp);

for(i=0;i<strsLen;i++){

strcat(res,strs[i]);

}

return res;

}

发表于 2024-04-16 12:25:38 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        // write code here
        if(strs == null || strs.length < 1) {
            return null;
        }
        PriorityQueue<String> queue=new PriorityQueue<>(new Comparator<String>(){
            public int compare(String s1,String s2){
                return (s1+s2).compareTo(s2+s1);
            }
        });
        for(int i=0;i<strs.length;i++){
            queue.add(strs[i]);
        }
        StringBuilder str=new StringBuilder();
        while(!queue.isEmpty()){
            str.append(queue.poll());
        }
        return str.toString();
    }
}

发表于 2023-05-18 19:48:54 回复(0)

小谷围做题家

package main

import "sort"
import "strings"

/**
 * 
 * @param strs string字符串一维数组 the strings
 * @return string字符串
*/
func minString( strs []string ) string {
    sort.Slice(strs,func(i,j int)bool{
        if strs[i]+strs[j]<strs[j]+strs[i]{
            return true
        }
        return false
    })
    return strings.Join(strs,"") 
}

发表于 2023-03-08 18:36:29 回复(0)

Python 3

牛客962313693号

一行

from functools import cmp_to_key

class Solution:
def minString(self , strs: List[str]) -> str:
# write code here
return ''.join(sorted(strs,key = cmp_to_key(lambda a,b: 1 if a+b>b+a else -1)))

发表于 2022-07-29 16:04:56 回复(0)

Java

pickpig

import java.util.*;


public class Solution {
    public String minString (String[] strs) {
        //Array.sort() 使用自定义比较器Comparator,比较两个元素(a,b)，
        //若返回值为正数则说明发生交换,即大于0,Comparator接收返回值为正数，就会交换a和b
        Arrays.sort(strs,(a,b) -> {
            return (a + b).compareTo(b + a);
        });
//         Arrays.sort(strs,(a,b) -> ((a + b).compareTo((b + a))));
        StringBuilder sb = new StringBuilder();
        for(String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }
}

发表于 2022-06-28 13:57:56 回复(0)

Java

冰冰中雨

import java.util.*;

public class Solution {
/**
*
* @param strs string字符串一维数组 the strings
* @return string字符串
*/
public String minString (String[] strs) {
StringBuilder str = new StringBuilder();
strs = strSort(strs,0,strs.length-1);
// write code here
for(int i=0;i<strs.length;i++){
str.append(strs[i]);
}
String s = str.toString();
return s;
}
public String[] strSort(String[] str,int start ,int end){
if(start==end){
return new String[]{str[start]};
}
int mid =start + (end-start)/2;
String[] left = strSort(str,start,mid);
String[] right = strSort(str,mid+1,end);
String[] newArr = new String[left.length+right.length];
int n=0,r=0,l=0;
while(r<right.length&&l<left.length){
if(compare(left[l],right[r])){
newArr[n++]=left[l++];
}else{
newArr[n++]=right[r++];
}
}

while(l<left.length){
newArr[n++]=left[l++];
}
while(r<right.length){
newArr[n++]=right[r++];
}
return newArr;

}
public boolean compare(String s,String t){
int n=0;
while(s.length()>n&&t.length()>n){
if(s.charAt(n)<t.charAt(n)){
return true;
}else if(s.charAt(n)>t.charAt(n)){
return false;
}
n++;
}
if(s.length()==n){
return true;
}
return false;
}

}

不晓得为什么不行?先排序,然后再拼接.

发表于 2022-04-06 23:14:06 回复(0)

Java

我难顶了

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        // write code here
        Arrays.sort(strs, (a,b) -> ((a+b).compareTo((b+a))));
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            sb.append(s);
        }
        return sb.toString();
    }
}

发表于 2022-04-05 17:05:33 回复(0)

Java

双马饮泉

public String minString (String[] strs) {
    // write code here
    StringBuffer sb = new StringBuffer();
    Arrays.sort(strs, new Comparator<String>(){
        @Override
        public int compare (String s1, String s2) {
            return (s1+s2).compareTo(s2+s1);
        }
    });

    for (String s:strs) {
        sb.append(s);
    }

    return sb.toString();
}

发表于 2021-08-03 10:32:15 回复(0)

害群之马

运行时间：61ms超过100.00% 用C++提交的代码

占用内存：6704KB超过91.69%用C++提交的代码

bool cmp(string& a, string& b){
        // ab>ba return true
        // ab<ba or ab==ba return false
         int A=a.size();
         int B=b.size();
        for(int i=0;i<=A+B-2;i++){
            char abi = i<A ? a[i] : b[i-A]; 
            char bai = i<B ? b[i] : a[i-B];
            if(abi<bai) return true;
            if(abi>bai) return false;
        }
        return false;
}
class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */

    string minString(vector<string>& strs) {
    // write code here
    sort(strs.begin(), strs.end(), cmp);
    string res;
    for (auto i : strs) {
        res += i;
    }
    return res;
}
};

编辑于 2021-06-09 13:54:14 回复(0)

漫漫云天自翱翔

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

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
    string minString(vector<string>& strs) {
	// write code here
	sort(strs.begin(), strs.end(), cmp);
	string res;
	for (auto i : strs) {
		res += i;
	}
	return res;
}
};

发表于 2021-05-03 13:54:02 回复(0)

Java

学习算法脑壳疼

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        // write code here
        if(strs==null){
            return null;
        }
        return stringsort(strs);
    }
    public class MinComparator implements Comparator<String>{
        public int compare(String o1,String o2){
            return (o1+o2).compareTo(o2+o1);
        }
    }
    public String stringsort(String[] str){
        PriorityQueue<String> minPriorityQueue=new PriorityQueue<>(new MinComparator());
        for(int i=0;i<str.length;i++){
            minPriorityQueue.add(str[i]);
        }
        StringBuilder ans=new StringBuilder();
        for(int i=0;i<str.length;i++){
            ans.append(minPriorityQueue.poll());
        }
        return ans.toString();
    }
}

发表于 2021-04-29 15:45:11 回复(0)

~凝檬

超时：
from functools import cmp_to_key
class Solution:
    def minString(self , strs ):
        # write code here
        def cmpp(s1,s2):
            if s1+s2 > s2+s1:
                return 1
            else:
                return -1

        strs = sorted(strs,key=cmp_to_key(cmpp))
        return ''.join(strs)

发表于 2020-12-14 09:29:30 回复(0)

一生ok

function minString( strs ) {
  strs.sort()
  return strs.join('')
}

发表于 2020-09-11 11:23:23 回复(1)

提交观点

问题信息

贪心

难度：

13条回答 67收藏 2906浏览

通过挑战的用户

查看代码

Andy9898

2023-03-14 19:53:45
K乀

2023-03-11 15:06:38
GeekExp...

2023-02-20 13:32:09
牛客64445...

2023-02-13 17:38:53
One Peach

2023-01-06 15:21:49

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

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题