如何从列表中取出按字母顺序排列的最长子字符串？

Question

例如，初始列表L=["by","article","circle","for","line","dance","effort"]，我想要取出["article","circle","for","line"]作为结果。因为L中的第一个字母是(b,a,c,f,l,d,e)，并且(a,c,f,l)的顺序比(d,e)的顺序更长，所以结果是["article","circle","for","line"]。如何修复我的代码？由于我是新手，所以我对sorted()和嵌套循环感到困惑。

def find_longest_consisting(test_case):
    if not test_case:
        return []
    result = []
    for i in range(len(test_case)):
        for j in range(i + len(result) + 1):
            substring = test_case[i:j]
            if len(substring) != (j - i):
                break
            if sorted(substring) == list(substring):
                result = substring
    return result

test_cases = ["by","article","circle","for","line","dance","effort"]
test_result = find_longest_consisting(test_cases)
print(test_result)

- antrous

Answer 1

最快的方法是保持一个“最长”列表，并在遇到排序更改时将其长度与当前子列表进行比较，如果当前子列表更长，则将其分配给最长的那个。这只需要对列表进行一次迭代即可得到结果。

def longest_group(lst):
    longest = []
    current = lst[:1]
    for i in range(1, len(lst)):
        if lst[i][0] <= lst[i-1][0]:
            if len(current) > len(longest):
                longest = current
            current = [lst[i]]
        else:
            current.append(lst[i])
    if len(current) > len(longest):
        longest = current
    return longest

print(longest_group(["by","article","circle","for","line","dance","effort"]))
print(longest_group(["zoo","slack","egg"]))

输出：

['article', 'circle', 'for', 'line']
['zoo']

对于您的["by","article","circle","for","line","dance","effort"]列表，使用这种方法比对列表中所有组合进行排序要快10倍。请查看https://rextester.com/JEJOAE73859获取演示。

- Nick

---

分配一个新列表比简单地切片输入要慢大约2倍。https://rextester.com/HEN61598 - Samwise

Answer 2

一个简单的替代方法是使用 itertools.combinations 来检查不同子集，而不是自己进行嵌套循环：

from itertools import combinations
def longest_group(lst):
    return max((
        lst[a:b]
        for a, b in combinations(range(len(lst)+1), 2)
        if sorted(lst[a:b]) == lst[a:b]
    ), key=len) if lst else lst

如果速度比简单性更重要，那么最快的方法是迭代列表并跟踪对应于最长排序片段的范围。

def longest_group(lst):
    a, b, i = 0, 0, 0
    for j, e in enumerate(lst[1:]):
        if e < lst[j]:
            if j - i > b - a:
                a, b = i, j
            i = j + 1
    if len(lst) - i > b - a + 1:
        a, b = i, len(lst)
    return lst[a:b+1]

- Samwise

---

这比简单迭代列表慢大约10倍。https://rextester.com/JEJOAE73859 - Nick

添加了一个更加优化的版本。 ;) - Samwise

很棒 - OP正在得到一个更好的解决方案。唯一的缺点是longest_group(["zoo","slack","egg"])的结果是['egg']，而不是所需的['zoo']（请参见编辑历史记录）。 - Nick