在给定字符串中查找字母按字母顺序排列的最长子串

Question

在执行我的代码时，我总是得到最长的字符串加上下一个字母。例如，如果我使用

s = 'azcbobobegghakl' 

我会得到"beggha"作为最长的字符串，而正确的答案应该是"beggh"。这个问题在我尝试的所有随机字母字符串中都出现了。

我发现多出来的字母是在“result += letters”这行代码执行后被加上的，但我不太确定该怎么修复。以下是我的代码：

s = 'azcbobobegghakl'
result = []
final = []
for letters in s:
    result += letters
    if result == sorted(result) and len(result) >= len(final):
        final=result
    elif result != sorted(result): 
        result = [result[len(result)-1]]
print "".join(final)

Answer 1

你需要解决几个问题。第一个是，当你使用...

final = result

这不仅仅是把结果中的值赋给final。它实际上是把变量'final'指向了一个内存地址，这个地址存储着'result'所指向的列表。所以如果'result'发生了变化，'final'也会跟着变化。要把'result'中的值赋给'final'，你可以使用...

final = result[:]

这样可以获取列表从头到尾的一部分的值。或者你也可以使用...

final = list(result)

在做完这个修改后，你需要在elif语句中去掉长度比较。

修改后的代码：

s = 'azcbobobegghakl'

result = []
final = []

for letters in s:
    result += letters
    if result == sorted(result) and len(result) >= len(final):
        final = list(result)
    elif result != sorted(result):
        result = [result[len(result)-1]]
print "".join(final)

Answer 2

这里的问题是 result 和 final 指向的是同一个列表。你可能会想，当你执行 result += letters 时，+= 会创建一个新的列表，但实际上并不会这样。

>>> x = [1,2]
>>> y = x
>>> x += [3]
>>> x
[1, 2, 3]
>>> y
[1, 2, 3]
>>> x is y
True

但是，当你使用 x = x + [3] 时：

>>> x = [1,2]
>>> y = x
>>> x = x + [3]
>>> x
[1, 2, 3]
>>> y
[1, 2]
>>> x is y
False

想要了解这个行为的原因，可以查看 这个问题。这就是在你的 for 循环中发生的情况（编辑：在你原来的代码中），当 letters 是字符串中的最后一个 a 字符时：

1. 一开始，final 和 result 都指向 ['b', 'e', 'g', 'g', 'h']。
2. 在执行 result += 'a' 后，final 和 result 都指向 ['b', 'e', 'g', 'g', 'h', 'a']。
3. 现在进入 elif 代码块，result 将指向一个新的列表 ['a']，而 final 仍然指向 ['b', 'e', 'g', 'g', 'h', 'a']。
4. 在这之后，final 将不会再被更新了。

因此，你原来的代码（在你编辑之前）可以通过将

result += letters

改为

result = result + [letters] 来修复：

s = 'azcbobobegghakl'
result = []
final = []
for letters in s:
    result = result + [letters]        
    if result == sorted(result) and len(result) >= len(final):
        final=result            
    elif result != sorted(result):
        result = [result[len(result)-1]]        

print(final)