按字母顺序查找最长子串

Question

编辑：我知道已经在SO中询问了一个具有类似任务的问题，但我有兴趣在这段特定代码中找出问题。我也知道这个问题不用递归就能解决。

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

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

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

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

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

经过一段时间的挣扎，我不知道这些字符串有什么特别之处，导致了这个错误。

这是我的代码：

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]

Answer 1

在你的代码中有很多东西需要改进，但是为了让它工作，你需要做最少的修改。问题是在循环中应该有if last_pos(i) != None:（而不是i+1），并且应该将diff（而不是diff - 1）与maxLen进行比较。请阅读其他答案，学习如何做得更好。

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

Answer 2

您可以使用嵌套的for循环、切片和sorted。如果字符串不全是小写，则可以在使用str.lower进行比较之前将子字符串转换为小写：

def solve(strs):
  maxx = ''
  for i in xrange(len(strs)):
      for j in xrange(i+1, len(strs)):
          s = strs[i:j+1]
          if ''.join(sorted(s)) == s:
              maxx = max(maxx, s, key=len)
          else:
              break
  return maxx

输出：

>>> solve('hixwluvyhzzzdgd')
'luvy'
>>> solve('eseoojlsuai')
'jlsu'
>>> solve('drurotsxjehlwfwgygygxz')
'ehlw'

Answer 3

给你。这是你想要的。一次通过，不需要递归。

def find_longest_substring_in_alphabetical_order(s):
    groups = []
    cur_longest = ''
    prev_char = ''
    for c in s.lower():
        if prev_char and c < prev_char:
            groups.append(cur_longest)
            cur_longest = c
        else:
            cur_longest += c
        prev_char = c
    return max(groups, key=len) if groups else s

使用它：

>>> find_longest_substring_in_alphabetical_order('hixwluvyhzzzdgd')
'luvy'
>>> find_longest_substring_in_alphabetical_order('eseoojlsuai')
'jlsu'
>>> find_longest_substring_in_alphabetical_order('drurotsxjehlwfwgygygxz')
'ehlw'

注意：它可能会在奇怪的字符上断开，只使用您建议的输入进行了测试。既然这是一个“家庭作业”问题，我会给你留下原样的解决方案，虽然还有一些优化要做，我想让它有点可以理解。