如何獲得最長的按字母順序排列的子字符串

我想寫一個函數，它返回字母按字母順序出現的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

來源

2016-09-16 A.E

如果'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

我希望這會幫助你。

來源

2016-09-16 18:41:22

非常感謝你@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))

來源

2016-09-16 19:05:41 wim

如何獲得最長的按字母順序排列的子字符串

回答

相關問題