题目
给定一个字符串类型的数组 strs , 找到一种拼接方式, 使得把所有字符串拼接起来之后形成的字符串具有最低的字典序.
题解
不可通过将各个数组元素按字典序排列再拼接的方式来解, 如对数组 ['b', 'ba'] 来说, 若按元素字典序来排列将得到 bba , 而实际上该结果并没有 bab 小, 故这种做法不可取.
本题应比较 str1 + str2 和 str2 + str1 的字典序大小, 以此为标准重写比较函数, 排序后拼接即可.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class LowestLexicography {
public static String lowestString(String[] strs) {
if (strs == null || strs.length == 0) {
return null;
}
Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));
String result = "";
for (String str : strs) {
result += str;
}
return result;
}
}
|
Python
以冒泡排序为例
1
2
3
4
5
6
7
| def get_lowest_lexicography(strings):
for i in range(len(strings)):
for j in range(len(strings) - 1):
if strings[j] + strings[j + 1] > strings[j + 1] + strings[j]:
strings[j], strings[j + 1] = strings[j + 1], strings[j]
return "".join(strings)
|
Go
1
2
3
4
5
6
7
8
9
10
11
| func getLowestLexicography(strs []string) string {
for i := 0; i < len(strs); i++ {
for j := 0; j < len(strs)-1; j++ {
if strs[j]+strs[j+1] > strs[j+1]+strs[j] {
strs[j], strs[j+1] = strs[j+1], strs[j]
}
}
}
return strings.Join(strs, "")
}
|