14.3:给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中字典序最小的结果

给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中字典序最小的结果

贪心写法

首先注意的一点是：如果两个字符串的长度相同，“abc”，“abd”，肯定是“abc”的字典序最小，放在前面。拼接的结果是abcabd也是最小的，

当两个字符串的长度不相同时“b”，“bac”，计算机进行字典序比较的时候，会将“b”后面补上最小的ASCII，即变成 “b00” 与 “bac” 进行比较。此时“b”小放前面，此时拼接的结果是：bbac，但是bbac > bacb所以这样拼接有问题。所以需要写一个我们自己的比较器。

思路：
1：将字符串数组进行排序，排序的标准就是我们自己写的比较器（两个字符串进行拼接，拼接结果小的字符串放前面）；

注意这个地方要有传递性才可以，比如说：( 1<10 && 10 < 20 ) --> (1 < 20) , 同理： (ab < abc && abc < abcg) --> ab < abcg

只有具有传递性，这个数组的排序才是有效的。至于传递性的证明，不需要自己证，写一个对数器，用实验的方法来证明自己的假设。

2：遍历整个数组，将数组中的结果拼接起来。

3：返回这个结果。

//贪心写法public static String lowestString2(String[] strs) {if (strs == null || strs.length == 0) {return "";}Arrays.sort(strs, new MyComparator());String ans = strs[0];for (int i = 1; i < strs.length; i++) {ans = ans.concat(strs[i]);}return ans;}public static class MyComparator implements Comparator<String> {@Overridepublic int compare(String o1, String o2) {// compareTo方法是用来比较两个字符串的字典顺序。-----------------------------**--// 如果返回值小于0，则表示(o1 + o2)小于(o2 + o1)，// 如果返回值等于0，则表示两者相等，// 如果返回值大于0，则表示(o1 + o2)大于(o2 + o1)。return (o1 + o2).compareTo(o2 + o1);}}

暴力写法

思路：总思路就是：给我一个字符串数组，将所有可能的情况给串起来，然后返回字典序最小的拼接情况。

我们需要一个容器来存放所有可能的结果：这个容器可以用TressSet,因为对于字符串他会自动的按字典序进行由小到大的排序

如何求得所有的可能情况：

		for (int index = 0; index < strs.length; index++) {String first = strs[index];//每一个字符串作为头的情况。String[] nexts = removeIndex(strs, index); //除去头以后剩下的字符串组成的数组。TreeSet<String> next = process(nexts); //通过递归调用，返回的是一个容器，里面存褚着所有的除去头以外的字符串。for (String cur : next) { // 将头节点都给安上。ans.add(first.concat(cur));}}

//暴力写法// lowestString1 : 返回所有可能的拼接结果中字典序最小的结果public static String lowestString1(String[] strs) {if (strs == null || strs.length == 0) {return "";}TreeSet<String> set = process(strs);return set == null || set.size() == 0 ? "" : set.first();}// process : strs中所有字符串的可能情况全排列，返回所有可能情况。public static TreeSet<String> process(String[] strs) {TreeSet<String> ans = new TreeSet<>();if (strs == null || strs.length == 0) {ans.add("");return ans;}for (int index = 0; index < strs.length; index++) {String first = strs[index];String[] nexts = removeIndex(strs, index);TreeSet<String> next = process(nexts);for (String cur : next) {ans.add(first.concat(cur));}}return ans;}public static String[] removeIndex(String[] strs, int index) {String[] ans = new String[strs.length - 1];int ansIndex = 0;for (int i = 0; i < strs.length; i++) {if (i != index) {ans[ansIndex++] = strs[i];}}return ans;}

比较器

做贪心的题目比较器是很重要的，因为为了避免证明，我们需要通过实验的方法来验证我们的答案。

// -------------------------------- for test -------------------------------public static void main(String[] args) {int testTime = 10000;int strArrayLength = 5;int strLength = 5;System.out.println("test begin");for (int i = 0; i < testTime; i++) {String[] arr1 = generateRandomStringArray(strArrayLength, strLength);String[] arr2 = copyStringArray(arr1);if (!lowestString1(arr1).equals(lowestString2(arr2))) {System.out.println(arr1);System.out.println(arr2);System.out.println("ooops");}}System.out.println("finish");}public static String[] generateRandomStringArray(int strArrayLength, int strLength) {String[] string = new String[(int) (Math.random() * strArrayLength + 1)];for (int i = 0; i < string.length; i++) {char[] c = new char[(int) (Math.random() * strLength + 1)];int a = (int) (Math.random() * 26); //[0,25]for (int j = 0; j < c.length; j++) {c[j] = (Math.random() < 0.5 ? (char) (65 + a) : (char) (95 + a));}string[i] = c.toString();}return string;}public static String[] copyStringArray(String[] ans) {String[] ret = new String[ans.length];for (int i = 0; i < ans.length; i++) {ret[i] = ans[i];}return ret;}
}