拼接最小字典序

题目

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

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

思路

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

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

重点：证明比较的有效性，根据comparable API,需要满足以下三个条件：

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
for all xand y. (This implies that x.compareTo(y) must throw an exception iff y.compareTo(x) throws an exception.)(对称性)

The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.(传递性)

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.(不知道这叫什么性...数学渣，还请读者赐教)

证明过程
证明最关键的步骤是证明这种比较的方式具有传递性。
假设有a,b,c三个字符串，他们有如下的关系：
a.b < b.a
b.c < c.b
所谓传递性证明是指，如果有以上的两个关系，能否证明 a.c < c.a
证明传递性过程：
字符串a,b的连接记为a.b，如果将字符串看做一个K进制数，那么字符串之间的加减乘除都可以按照数字的方式进行。
那么a.b这个字符串中a作为高位，b作为低位，可以进行如下的替换
a.b = a(K^length(b))+b。其中a(K^length(b))表示，a这个K进制数，向左位移了b的长度。
我们现在把K^length(b)记为moveBit(b)，则a.b = amoveBit(b)+b，那么
a.b < b.a => amoveBit(b)+b < bmoveBit(a)+a 不等式1
b.c < c.b => bmoveBit(c)+c < cmoveBit(b)+b 不等式2
现在要证明a.c < c.a，也就是证明amoveBit(c)+c < cmoveBit(a)+a
我们把不等式1的左右两边同时减去b再乘以c，则不等式1可以变形为：
amoveBit(b)c < bmoveBit(a)c+ac-bc
我们把不等式2的左右两边同时减去b再乘以a，则不等式2可以变形为：
bmoveBit(c)a+ca-ba < cmoveBit(b)a
现在a,b,c都是K进制数，所以服从乘法交换律。
所以不等式1中的amoveBit(b)c等于不等式2中的cmoveBit(b)a。
所以，bmoveBit(c)a+ca-ba < bmoveBit(a)c+ac-bc
所以，bmoveBit(c)a-ba < bmoveBit(a)c-bc
所以，amoveBit(c)-a < cmoveBit(a)-c
所以，amoveBit(c)+c < c*moveBit(a)+a => a.c < c.a
证明a.c < c.a完成。

Java代码如下:

import java.util.*;
 
public class Prior {
    public class MyComparator implements Comparator<String> {
        public int compare(String a, String b) {
            return (a + b).compareTo(b + 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();
    }
}