拼接最小字典序

题目

对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。

测试样例：["abc","de"],2
"abcde"

思路

典型的贪心算法题，把数组元素依次从小到大拼接起来就是字典序最小的串。但是如何定义数组元素之间的大小关系呢？看起来字典序是个不错的选择，abc<de,拼接起来正好就是答案。但是对于{b,ba}来说，bab要比bba小，字典序是错误的。

所以这里我们定义比较关系如下：(+代表字符串拼接)
A+B<B+A => A<B

Java代码如下:

import java.util.*;
 
public class Prior {
    public class MyComparator implements Comparator<String> {
        public int compare(String a, String b) {
            return (a +  + a);
        }
    }
 
    public String findSmallest(String[] strs, int n) {
        if (strs == null || n == 0) {
            return "";
        }
        // 根据新的比较方式排序
        Arrays.sort(strs, new MyComparator());
        StringBuilder res = new StringBuilder();
        for (String str:strs) {
            res.append(str);
        }
        return res.toString();
    }
}