假设字符串数组是str[] = {"ab","cd","ef"},很明显答案就是”abcdef“最小,其实这是一道贪心问题,我的想法是将字符串数组进行内的字符串数组进行排序,这个大思路是没错的,但问题是怎么排序,str[i] < str[j]?这样其实不行,举个反例str[] = {"b","ba"},如果按照那个贪心策略排序,得到的答案是"bba",但实际上“bab”更小,后来仔细以想,贪心策略应该是str[i] + str[j] < str[j] + str[i],有兴趣的大家可以下去证明,还是比较好证的
import java.util.*;
public class Main {
public static class MyCompara implements Comparator<String> {
public int compare(String s1, String s2) {
String tmp1 = s1 + s2;
String tmp2 = s2 + s1;
return tmp1.compareTo(s2);
}
}
public static String minString(String[] str) {
String res = "";
Arrays.sort(str,new MyCompara());
for(int i = 0;i < str.length;i++)
res += str[i];
return res;
}
public static void main(String[] args) {
System.out.println(minString(new String[] {"ab","ef","cd"}));
}
}