拼接顺序

题目：拼接顺序（算法课第七课）

给定一个字符串类型的数组strs，请找到一种拼接顺序，使得将所有的字符串拼接起来组成的大字符串是所有可能性中字典顺序最小的，并返回这个大字符串。

字典序

字符串字典序：

1. 当字符串长度相等时 。 从左向右。 c>a （c的ascll码大于a）后边的不需要判断 确定 ca 大于 ac

ca > ac

2. 当字符串长度不等时 。 长度短的字符串 自动右边补零 ,扩大到相等长度再比较

cac < d

d = d00，cac < d00

举例

strs = [“abc”, “de”]，可以拼接成 “abcde”，也可以拼接成 “deabc”，但前者的字典顺序更小，所以返回 abcde
strs = [“b”, “ba”]，可以拼成 “bba”,也可以拼成 “bab”，但后者的字典顺序更小，所以返回bab

基本思路

直接串起来

有一种思路为：
先把strs中的字符串按照字典顺序排序，然后将串起来的结果返回。这么做是错误的，例如【举例】中的第二条，按照字典顺序排应该是b、ba，串起来的结果是bba，但是正确答案是bab。所以这个思路行不通。正确的排序方式如下：

选择前缀

假设两个字符分别是a，b。a和b拼起来的字符串表示为a.b，那么如果a.b的字典顺序小于b.a，就把a放在前面，否则把b放在前面。每两个字符之间都按照这个标准进行比较，以此标准排序后，最后串起来的结果就是正确答案。证明太复杂，省略。

代码

import java.util.Arrays;
import java.util.Comparator;

public class LowestLexicography {

	public static class MyComparator implements Comparator<String> {
		@Override
		public int compare(String a, String b) {//a做前缀和b做前缀，那个更小
			return (a + b).compareTo(b + a);
		}
	}

	public static String lowestString(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		Arrays.sort(strs, new MyComparator());
		String res = "";
		for (int i = 0; i < strs.length; i++) {
			res += strs[i];
		}
		return res;
	}

	public static void main(String[] args) {
		String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };
		System.out.println(lowestString(strs1));

		String[] strs2 = { "ba", "b" };
		System.out.println(lowestString(strs2));
	}
}

输出：

bwjibwjibwjijp
bab