按字母顺序查找最长的子串 [英] Finding longest substring in alphabetical order

问题描述

编辑:我知道在 SO 中已经提出了类似任务的问题，但我有兴趣在这段特定的代码中找出问题所在.我也知道这个问题可以不用递归解决.

EDIT: I am aware that a question with similar task was already asked in SO but I'm interested to find out the problem in this specific piece of code. I am also aware that this problem can be solved without using recursion.

任务是编写一个程序，该程序将查找(并打印)字母按字母顺序出现的最长子字符串.如果发现超过 1 个同样长的序列，则应打印第一个.例如，字符串 abczabcd 的输出将是 abcz.

The task is to write a program which will find (and print) the longest sub-string in which the letters occur in alphabetical order. If more than 1 equally long sequences were found, then the first one should be printed. For example, the output for a string abczabcd will be abcz.

我已经用递归解决了这个问题，它似乎通过了我的手动测试.但是，当我运行生成随机字符串的自动化测试集时，我注意到在某些情况下，输出是不正确的.例如:

I have solved this problem with recursion which seemed to pass my manual tests. However when I run an automated tests set which generate random strings, I have noticed that in some cases, the output is incorrect. For example:

如果 s = 'hixwluvyhzzzdgd'，则输出是 hix 而不是 luvy

if s = 'hixwluvyhzzzdgd', the output is hix instead of luvy

如果 s = 'eseoojlsuai'，输出是 eoo 而不是 jlsu

if s = 'eseoojlsuai', the output is eoo instead of jlsu

如果 s = 'drurotsxjehlwfwgygygxz'，输出是 dru 而不是 ehlw

if s = 'drurotsxjehlwfwgygygxz', the output is dru instead of ehlw

经过一段时间的挣扎，我无法弄清楚导致错误的这些字符串有何特别之处.

After some time struggling, I couldn't figure out what is so special about these strings that causes the bug.

这是我的代码:

pos = 0
maxLen = 0
startPos = 0
endPos = 0


def last_pos(pos):
    if pos < (len(s) - 1):
        if s[pos + 1] >= s[pos]:
            pos += 1
            if pos == len(s)-1:
                return len(s)
            else:
                return last_pos(pos)
        return pos


for i in range(len(s)):
    if last_pos(i+1) != None:
        diff = last_pos(i) - i
    if diff - 1 > maxLen:
        maxLen = diff
        startPos = i
        endPos = startPos + diff

print s[startPos:endPos+1]

推荐答案

您的代码有很多需要改进的地方，但只需进行最少的更改即可使其正常工作.问题是你应该有 if last_pos(i) != None: 在你的 for 循环中(i 而不是 i+1) 并且您应该将 diff(不是 diff - 1)与 maxLen 进行比较.请阅读其他答案以了解如何做得更好.

There are many things to improve in your code but making minimum changes so as to make it work. The problem is you should have if last_pos(i) != None: in your for loop (i instead of i+1) and you should compare diff (not diff - 1) against maxLen. Please read other answers to learn how to do it better.

for i in range(len(s)):
    if last_pos(i) != None:
        diff = last_pos(i) - i + 1
    if diff > maxLen:
        maxLen = diff
        startPos = i
        endPos = startPos + diff - 1

这篇关于按字母顺序查找最长的子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！