如何获得最长的按字母顺序排列的子字符串

问题描述：

我想写一个函数，它返回字母按字母顺序出现的s中最长的子字符串。例如，如果s = 'azcbobobegghakl'，函数应返回'beggh'如何获得最长的按字母顺序排列的子字符串

这是我的函数，它仍然不完整，但它不返回sub的列表; 返回的错误是：

"IndexError: string index out of range"

def longest_substring(s): 
    sub=[] 
    for i in range (len(s)-1): 
     subs=s[i] 
     counter=i+1 
     while ord(s[i])<ord(s[counter]): 
      subs+=s[counter] 
      counter+=1 
     sub.append(subs) 
    return sub

如果'counter'超过'LEN（S）'？在'while'循环中，我认为你的情况在这个输入中失败：'acdb'，因为你试图比较所有剩余的字符和第一个字符'a'，所以它给出的答案是'acdb'这是错误的。答案应该是'acd'我认为.. –

https://en.wikipedia.org/wiki/Longest_increasing_subsequence –

@ cricket_007实际上并不正确...子序列可以跳过元素！ – wim

答

这是不是最佳的（在线性时间O(n)作品），但我做了一些修改你的代码（在Python 3）：

def longest_substring(s): 
    length = len(s) 
    if length == 0 :   # Empty string 
     return s 
    final = s[0] 
    for i in range (length-1): 
     current = s[i] 
     counter = i+1 
     while counter < length and ord(s[i]) <= ord(s[counter]): 
      current += s[counter] 
      counter +=1 
      i+=1 
     if len(final) < len(current): 
      final = current 
    return final 
s = 'azcbobobegghakl' 
print(longest_substring(s))

输出：

beggh

Modifications:

You are comparing character with fixed position i.e. in while loop you are incrementing only counter not i so I incremented the ith position also.(So we avoid checking the characters which are already checked, So it does this in linear time O(n) I think..)

Also you are only checking less than for condition while ord(s[i])<ord(s[counter]): But you also have to check for equals too.

You created one list where you append every sequence which is unnecessary unless you want do any other calculations on the sequence, So I take string and if previous sequence's length is small then I updated it with new sequence.

注意：如果两个序列的长度相同，则第一个出现的序列显示为输出。

其他输入：

s = 'acdb'

输出：

acd

我希望这会帮助你。

非常感谢你@Kalpesh –

这段代码是做什么的？：如果len（sub）

@ A.E。如果当前序列长度大于以前的最大序列，则将其分配给答案。 –

答

这是可以做到O（n）的倒也干脆：

def gen(s): 
    prev = '' 
    for c in s: 
     if c >= prev[-1:]: 
      prev += c 
     else: 
      yield prev 
      prev = c 
    if prev: 
     yield prev 

print(max(gen('azcbobobegghakl'), key=len))

如何获得最长的按字母顺序排列的子字符串

相关推荐