給定一個由字符串組成的數(shù)組strs，必須把所有的字符串拼接起來，返回所有可能的拼接結(jié)果中字典序最小的結(jié)果

貪心寫法

首先注意的一點是：如果兩個字符串的長度相同，“abc”，“abd”，肯定是“abc”的字典序最小，放在前面。拼接的結(jié)果是abcabd也是最小的，

當(dāng)兩個字符串的長度不相同時“b”，“bac”，計算機進行字典序比較的時候，會將“b”后面補上最小的ASCII，即變成 “b00” 與 “bac” 進行比較。此時“b”小放前面，此時拼接的結(jié)果是：bbac，但是bbac > bacb所以這樣拼接有問題。所以需要寫一個我們自己的比較器。

思路：
1：將字符串?dāng)?shù)組進行排序，排序的標(biāo)準(zhǔn)就是我們自己寫的比較器（兩個字符串進行拼接，拼接結(jié)果小的字符串放前面）；

注意這個地方要有傳遞性才可以，比如說：( 1<10 && 10 < 20 ) --> (1 < 20) , 同理： (ab < abc && abc < abcg) --> ab < abcg

只有具有傳遞性，這個數(shù)組的排序才是有效的。至于傳遞性的證明，不需要自己證，寫一個對數(shù)器，用實驗的方法來證明自己的假設(shè)。

2：遍歷整個數(shù)組，將數(shù)組中的結(jié)果拼接起來。

3：返回這個結(jié)果。

//貪心寫法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);}}

暴力寫法

思路：總思路就是：給我一個字符串?dāng)?shù)組，將所有可能的情況給串起來，然后返回字典序最小的拼接情況。

我們需要一個容器來存放所有可能的結(jié)果：這個容器可以用TressSet,因為對于字符串他會自動的按字典序進行由小到大的排序

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

		for (int index = 0; index < strs.length; index++) {String first = strs[index];//每一個字符串作為頭的情況。String[] nexts = removeIndex(strs, index); //除去頭以后剩下的字符串組成的數(shù)組。TreeSet<String> next = process(nexts); //通過遞歸調(diào)用，返回的是一個容器，里面存褚著所有的除去頭以外的字符串。for (String cur : next) { // 將頭節(jié)點都給安上。ans.add(first.concat(cur));}}

//暴力寫法// lowestString1 : 返回所有可能的拼接結(jié)果中字典序最小的結(jié)果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;}
}