Python：最长按字母顺序排列的子串

Posted on | In

这是edX上Introduction to Computer Science and Programming Using Python第一周的一个练习题，题目是这样的：给你一个由小写字母组成的字符串s，请你输出按字母顺序排列的最长的s的子串

示例输入：

1
2
3
azcbobobegghakl
fyfujnpe
zyxwvutsrqponmlkjihgfedcba

示例输出： 

1
2
3
beggh
jnp
z

下面是我的解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def longest_alphabetical_substring(s):
    start = 0   
    end = 0   
    length = 0   
    for i in range(len(s)-1):
        j = i
        while j != len(s)-1 and s[j] <= s[j+1]:
            j += 1     
        if j + 1 - i > length:             
            start = i
            end = j + 1 
            length = end - start
    return s[start:end]

第一块是初始化变量，主要是最长子串的起始下标、终止下标、长度。

第二块是字母顺序的判断以及最长子串的储存。

第一个循环是讲字符串的每一个字母当成起始字母来判断字母顺序，第二个循环在起始字母和下一个字母满足字母顺序之后继续判断，这里的j != len(s)-1是为了防止出现IndexError: string index out of range。如果不加上这个判断的话，当倒数第二个字母和最后一个字母满足字母顺序（此时j = len(s) - 2），j += 1之后再执行s[j] <= s[j+1]判断时，s [j+1] == s[len(s)]，所以必须加上j != len(s)-1。循环里if语句是判断，当前子串是否比已储存的子串长，如果长的话就替代掉。这里的j+1是由于字符串切片s[n:m]是指s的下标index满足：n <= index < m，加1之后才包含s[m]。

总的思路就是：

  1. 变量初始化
  2. 选择合适的遍历方式
  3. 判断是否满足条件
  4. 最优解的替换与储存 在这个题目中，如果一个字符串满足字母顺序，那么它的任意子串也满足字母顺序。所以把每个字符当子串的起始字符进行循环，出现不满足字母顺序时即把以这个字符为起始字符的最长满足字母顺序的子串与已有的最长子串相比，如果比已有的最长子串短就不必再增加子串长度，就可以把以这个字符为起始字符的更长的子串都舍掉。这样比枚举每一个子串，再判断要快很多。

参考：http://stackoverflow.com/questions/19604825/finding-the-longest-substring-in-alphabetical-order-from-a-given-string