求最小合并字符串 ---贪心算法

题目:给定一个字符串数组,合并这些字符串,由于不同的合并会产生不同的大小
要求: 求出最小的合并字符串
思路 : 误区---把字符串最小的放前面,这个是错误的(比如ab和a,是a更小,但是最小组合是aab而不是aba)
我们应该把数组组合后两两比较求出合并后可以最小的放前面
如要比较 aa 和ab谁应该放前面,则,前面不动,拼接另一个字符串,再进行比较
,也就是比较 aaab 和 abaa,aaab更小,所以需要的拼接结果是aaab

贪心问题:每次把最小的放前面

代码:

public class FindMinGroupInArrs {
    public static class myComparor implements Comparator<String>{
        @Override
        public int compare(String s1, String s2) {
            return (s1+s2).compareTo(s2+s1); //s1.compareTo(s2+s1)  正数代表前面大
        }
    }
    public static String returnMinSringGroup(String[] strs){
        if (strs==null){
            return "";
        }
        Arrays.sort(strs,new myComparor()); //Arrays.sort传入自己比较器后,正数代表交换,负数代表不交换
        String res="";
        for(int i=0;i<strs.length;i++){
            res+=strs[i];
        }
        return res;
    }

}