首页 > 试题广场 >

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

[编程题]拼接所有的字符串产生字典序最小的字符串
  • 热度指数：7005 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的字符串数组 strs ，请找到一种拼接顺序，使得数组中所有的字符串拼接起来组成的字符串是所有拼接方案中字典序最小的，并返回这个拼接后的字符串。

数据范围： ，
进阶：空间复杂度 ， 时间复杂度
示例1

输入

["abc","de"]

输出

"abcde"
示例2

输入

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

输出

"aab"

备注:

算法知识视频讲解
添加回答
唐氏综合征头像 唐氏综合征
java: 

   public String minString(String[] strs) {
        // write code here
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        return String.join("", strs);
    }


发表于 2024-06-11 09:27:53 回复(0)
C
牛客670170875号头像 牛客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)
Go
小谷围做题家头像 小谷围做题家 
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号头像 牛客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头像 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头像 一生ok 
function minString( strs ) {
  strs.sort()
  return strs.join('')
}

发表于 2020-09-11 11:23:23 回复(1)
提交观点

问题信息

贪心
难度：
14条回答 3306浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号