题解 | #拼接所有的字符串产生字典序最小的字符串#

import java.util.*;


public class Solution {
    
    // 方法一: 自定义一个比较器(最简单的方法)
    public class ComparaString implements Comparator<String> {
        @Override
        public int compare(String str1, String str2) {
            String str12 = str1 + str2;
            String str21 = str2 + str1;
            for (int i = 0; i < str12.length(); i++) {
                if (str12.charAt(i) < str21.charAt(i)) {
                    return -1;
                }
                else if (str12.charAt(i) > str21.charAt(i)) {
                    return 1;
                }
            }
            return 0;
        }
    }
    
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        // write code here
        
        // 一些特殊情况的处理
        if (1 == strs.length) {
            return strs[0];
        }
        
        // 方法一
        // Arrays.sort(strs, new ComparaString());
        // 方法二
        quickSort(strs, 0, strs.length - 1);
        
        // 定义一个 StringBuffer，用于存放最终的返回结果(因为 StringBuffer 的拼接效率比 String 的拼接效率高得多，所以这里我们使用 StringBuffer 对数组内的字符串进行拼接)
        StringBuffer res = new StringBuffer("");
        for (String str : strs) {
            res.append(str);
        }
        return new String(res);
    }
    
    // 方法二: 自己实现一遍快速排序算法(推荐)
    // 快排
    public void quickSort(String[] strs, int start, int end) {
        
        if (start >= end) {
            return;
        }
        
        // 荷兰国旗问题
        int l = start - 1; // 小于区域
        int r = end + 1; // 大于区域
        int cur = start; // 当前位置
        String tmp = strs[end]; // 比较的字符串
        while (cur < r) {
            if (comparaString(strs[cur], tmp) == -1) { // 小于
                String swap = strs[cur];
                strs[cur] = strs[l + 1];
                strs[l + 1] = swap;
                l++;
                cur++;
            }
            else if (comparaString(strs[cur], tmp) == 1) { // 大于
                String swap = strs[cur];
                strs[cur] = strs[r - 1];
                strs[r - 1] = swap;
                r--;
            }
            else { // 等于
                cur++;
            }
        }
        // 递归调用
        quickSort(strs, start, l);
        quickSort(strs, r, end);
        return;
    }
    // 自定义一个函数，实现两个字符串的大小比较
    public int comparaString(String str1, String str2) {
        String str12 = str1 + str2;
        String str21 = str2 + str1;
        for (int i = 0; i < str12.length(); i++) {
            if (str12.charAt(i) < str21.charAt(i)) {
                return -1;
            }
            else if (str12.charAt(i) > str21.charAt(i)) {
                return 1;
            }
        }
        return 0;
    }
}