在较长的字符串中查找最长的字母子字符串

Question

此代码查找字符串中最长的字母子串 (s)。

letter = s[0]      
best = ''          
for n in range(1, len(s)):    
    if len(letter) > len(best):
        best = letter
    if s[n] >= s[n-1]:
        letter += s[n]    
    else:                      
        letter = s[n]

它大部分时间都有效，但偶尔会给出错误的答案，我很困惑为什么它只是有时有效。例如当：

s='maezsibmhzxhpprvx'

它说答案是 "hpprv" 而它应该是 "hpprvx"。

另一种情况，当

s='ysdxvkctcpxidnvaepz'

它给出了答案"cpx"，而它本应该是"aepz"。

任何人都可以理解它为什么这样做吗？

Answer 1

你应该移动这张支票

if len(letter) > len(best):
    best = letter

在循环的剩余部分之后

Answer 2

逻辑几乎没问题，除了如果 letter 在最后一次循环迭代时增长（当 n == len(s) - 1 时），上次 best 没有改变。您可以在循环后插入另一个 best = letter 部分，或者重新仔细考虑程序结构，以免重复自己。

Answer 3

你的例程几乎没问题，这里是你的例程之间的一个小比较，固定的一个和另一个可能解决你问题的方法：

def buggy(s):
    letter = s[0]
    best = ''
    for n in range(1, len(s)):
        if len(letter) > len(best):
            best = letter
        if s[n] >= s[n - 1]:
            letter += s[n]
        else:
            letter = s[n]

    return best


def fixed(s):
    letter = s[0]
    best = ''
    for n in range(1, len(s)):
        if s[n] >= s[n - 1]:
            letter += s[n]
        else:
            letter = s[n]

        if len(letter) > len(best):
            best = letter

    return best


def alternative(s):
    result = ['' for i in range(len(s))]
    index = 0

    for i in range(len(s)):
        if (i == len(s) - 1 and s[i] >= s[i - 1]) or s[i] <= s[i + 1]:
            result[index] += s[i]
        else:
            result[index] += s[i]
            index += 1

    return max(result, key=len)


for sample in ['maezsibmhzxhpprvx', 'ysdxvkctcpxidnvaepz']:
    o1, o2, o3 = buggy(sample), fixed(sample), alternative(sample)
    print "buggy={0:10} fixed={1:10} alternative={2:10}".format(o1, o2, o3)

正如您在您的版本中看到的那样，内部循环条件的顺序不正确，您应该将第一个条件移动到循环的末尾。

在较长的字符串中查找最长的字母子字符串

Finding the longest alphabetical substring in a longer string

python

string

alphabetical