给定一个长度为 n 的字符串数组 strs ,请找到一种拼接顺序,使得数组中所有的字符串拼接起来组成的字符串是所有拼接方案中字典序最小的,并返回这个拼接后的字符串。
数据范围: ,
进阶:空间复杂度 , 时间复杂度
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(); } }
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,"") }
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(); } }
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(); } }
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(); }
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; } };
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; } };
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(); } }