按字母顺序查找最长子串

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

您可以使用嵌套的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'