题目:
给定一个由字符串组成的数组strs,
必须把所有的字符串拼接起来,
返回所有可能的拼接结果中,字典序最小的结果
1、暴力解决方案:
1.1、图解:
?
1.2、代码:
//方案一:(全排列,暴力解决)
public static String lowestString1(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
//存放全排列的结果
ArrayList<String> all = new ArrayList<>();
HashSet<Integer> use = new HashSet<>();
process(strs, use, "", all);
String lowest = all.get(0);
for (int i = 1; i < all.size(); i++) {
if (all.get(i).compareTo(lowest) < 0) {
lowest = all.get(i);
}
}
return lowest;
}
/**
* 功能描述
*
* @param strs 存放着所有的字符串
* @param use 已经使用过的字符串的下标,在use登记了,不要再使用了
* @param path 之前使用过的字符串,拼接成了一个path
* @param all 所有可能的拼接结果
*/
public static void process(String[] strs, HashSet<Integer> use, String path, ArrayList<String> all) {
if (use.size() == strs.length) {
all.add(path);
} else {
for (int i = 0; i < strs.length; i++) {
//如果该字符串还没有遍历过,那么就加入到set集合中。遍历之后,要移除掉
if (!use.contains(i)) {
use.add(i);
process(strs, use, path + strs[i], all);
use.remove(i);
}
}
}
}
?2、贪心解决方案:
2.1、图解:
2.2、代码:
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
//方案2:(贪心策略)
public static String lowestString2(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;
}
?
|