对字符串数组进行排序，使得任何其他字符串的子字符串均排在其后面。

Question

对字符串数组进行排序，使得任何其他字符串的子字符串均排在其后面。

4

我希望找到一个算法，可以对字符串数组进行排序，使得如果任何一个字符串（例如B）是另一个字符串（例如ABAC）的子字符串，则B应该排在ABAC之后。

例如：

假设这些字符串是：

abc
bc
zef
abcde

那么顺序将会是：

abcde, 
abc, 
bc 
and zef can come anywhere in the order.

- Sagar Mahour

1

你喜欢用哪种编程语言编写代码？另外，如果有两个字符串都包含子字符串“bc”，你希望将“bc”放在哪里？例如，有三个字符串：“abc”、“dbc”和“bc”。在这种情况下，你希望“bc”放在哪里？ - Kevin Ng

"bc" 可以在 "abc" 和 "dbc" 之后的任何位置，但是 "abc" 和 "dbc" 的顺序并不重要。 - Sagar Mahour

@KevinNg 任何编程语言或伪代码都可以，只要我能理解算法的工作原理，例如C、C++、Python、Java、PHP等。 - Sagar Mahour

构建一个 Trie 看起来是一个不错的方法。 - Pham Trung

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

排序算法基于比较值对。通常，编程语言允许使用比较函数提供内置的排序方法，该函数应该接受两个参数，并返回一个整数值，指示它们的相对顺序（-1、0或1）。

因此，请按照以下方式定义比较函数：

compare(a, b):
    if a is substring of b then return 1
    if b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

这个子字符串测试应该首先检查两个字符串的长度，以避免扫描字符串。因为当 a.length > b.length 时，a 不能是 b 的子字符串。或者您也可以明确地写出：

compare(a, b):
    if a.length <= b.length and a is substring of b then return 1
    if a.length >= b.length and b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

如果目标编程语言不支持此功能，则应编写自己的排序函数（例如QuickSort），并确保它可以使用这样的比较器，以便您可以替换（从标准实现开始）：

 if a < b

使用：

 if compare(a, b) < 0

关系的传递性

假设一下，编码在比较函数中的关系不是传递的，因此我们可以找到三个字符串a、b和c，满足以下条件：

compare(a, b) < 0
compare(b, c) < 0
但是：compare(c, a) <= 0

首先，注意一下这句话对三个字符串长度的要求：

compare(a, b) < 0 意味着 a.length >= b.length
compare(b, c) < 0 意味着 b.length >= c.length
compare(c, a) <= 0 意味着 c.length >= a.length

从前两个条件我们可以得出 a.length >= c.length，再结合第三个条件，我们可以得出所有三个字符串的长度相同。

现在我们有：

compare(a, b) < 0 意味着 a 在字母顺序上排在 b 前面
compare(b, c) < 0 意味着 b 在字母顺序上排在 c 前面
compare(c, a) <= 0 意味着 c 在字母顺序上排在 a 前面，或者等于 a。

这会导致矛盾。因此我们必须得出结论：关系具有传递性。