词典排序

Question

我正在做一个问题,即"连接单词以生成按字典顺序排列的最低字符串." 来自比赛.

以此字符串为例: jibw ji jp bw jibw

实际输出结果是: bw jibw jibw ji jp

当我对此进行排序时,我得到:bw ji jibw jibw jp.

这是否意味着这不是排序？如果它是排序,"词典"排序是否考虑将较短的琴弦推到后面或其他东西？

我一直在阅读关于lexigographical命令的一些阅读,我没有看到使用它的任何点或场景,你有吗？

Answer 1

看来你正在寻找的是更好地理解这个问题,所以让我说清楚.字符串的通常排序是词典排序.如果你将字符串[jibw,ji,jp,bw,jibw]排序成字典顺序,那么排序的序列是 [bw,ji,jibw,jibw,jp],这就是你得到的.所以你的问题不在于理解"词典"这个词; 你已经正确理解了.

你的问题是你误解了这个问题.这个问题不问你要排序的字典序的字符串.(如果确实如此,你通过排序得到的答案是正确的.)相反,它要求你生成一个字符串,通过以某种顺序连接输入字符串得到(即,使一个字符串没有空格),以便生成单个字符串字符串按字典顺序最小.

为了说明差异,请考虑通过连接排序序列和答案字符串获得的字符串:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

现在,当你比较这两个字符串时 - 注意你只是比较两个14个字符的字符串,而不是两个字符串序列 - 你可以看到正确的答案确实在字典上小于你的答案:你的答案以"bwjij"开头,正确的答案以"bwjib"开头,而"bwjib"以字典顺序出现在"bwjij"之前.

希望你现在明白这个问题.这根本不是一个排序问题.(也就是说,排序输入字符串不是问题.你可以通过置换和连接输入字符串对所有可能的字符串进行排序;如果输入字符串的数量很少,这是解决问题的一种方法.)