按字母順序查找最長的子字符串

Question

我想編寫一個按字母順序打印最長的子字符串的程序。

而且在關係的情況下，它打印第一個子字符串。

這裏是我寫的

import sys 
s1 = str(sys.argv[1]) 
alpha = "abcdefghijklmnopqrstuvwxyz" 

def longest_substring(s1): 
    for i in range(len(alpha)): 
     for k in range(len(alpha)): 
      if alpha[i:k] in s1: 
       return alpha[i:k] 

print("Longest substring in alphabetical order:", longest_substring(s1)) 

但是，它不工作，我不知道該怎麼辦的第二部分。

你能幫助我嗎？

Answer 1

這裏是你的代碼看起來應該達到你想要的東西：

#!/usr/bin/env python3.6 
import sys 
s1 = str(sys.argv[1]) 
alpha = "abcdefghijklmnopqrstuvwxyz" 
subs = [] 


def longest_substring(s1): 
    for i in range(len(alpha)): 
     for k in range(len(alpha)): 
      if alpha[i:k] in s1: 
       subs.append(alpha[i:k]) 
    return max(subs, key=len) 


print("Longest substring in alphabetical order:", longest_substring(s1)) 

你是正確返回該功能的第一個字母順序排列的子串你找到。在我的代碼中，我們將它們添加到列表中，然後打印出最長的一個。

Answer 2

除了建立所有可能的子串切片的列表，然後檢查字符串中存在哪一個，你可以建立一個所有連續子串的列表，然後取最大長度的列表。

這很容易通過使用該角色的ord與遞增計數器之間的差異對角色進行分組來完成;連續的字符會有一個不變的差異。 itertools.groupby用於執行分組：

from itertools import groupby, count 

alpha = "abcdefghijklmnopqrstuvwxyz" 
c = count() 

lst_substrs = [''.join(g) for _, g in groupby(alpha, lambda x: ord(x)-next(c))] 
substr = max(lst_substrs, key=len) 
print(substr) 
# abcdefghijklmnopqrstuvwxyz 

作爲@AdamSmith評論的，上述假設字符總是按字母順序排列。在它們可能不是的情況下，可以通過檢查組中的項目是按字母順序排列的執行順序：

from itertools import groupby, count, tee 

lst = [] 
c = count() 
for _, g in groupby(alpha, lambda x: ord(x)-next(c)): 
    a, b = tee(g) 
    try: 
     if ord(next(a)) - ord(next(a)) == -1: 
      lst.append(''.join(b)) 
    except StopIteration: 
     pass 
    lst.extend(b) # add each chr from non-alphabetic iterator (could be empty) 

substr = max(lst, key=len) 

Answer 3

假設子串包含按字母順序排列2點或更多的字符。所以你不僅應該返回第一次發生，而且要收集所有發現並且發現時間最長。我儘量保持你的想法一樣，但是這不是最有效的方法：

def longest_substring(s1): 
    res = [] 
    for i in range(len(alpha) - 2): 
     for k in range(i + 2, len(alpha)): 
      if alpha[i:k] in s1: 
       res.append(alpha[i:k]) 
    return max(res, key=len) 

Answer 4

你重新寫一個版本的itertools.takewhile採取二進制比較功能，而不是一元一個的。

def my_takewhile(predicate, starting_value, iterable): 
    last = starting_value 
    for cur in iterable: 
     if predicate(last, cur): 
      yield cur 
      last = cur 
     else: 
      break 

然後你可以小寫的話（因爲"Za"不按字母順序排列，但任何[A-Z]任何[a-z]之前按字母順序比較），並得到所有的子字符串。

i = 0 
substrings = [] 
while i < len(alpha): 
    it = iter(alpha[i:]) 
    substring = str(my_takewhile(lambda x,y: x<y, chr(0), it)) 
    i += len(substring) 
    substrings.append(substring) 

然後找到substrings中最長的子字符串。

result = max(substrings, key=len) 

Answer 5

備份並再次查看此問題。 1.你正在尋找的最大和應該基本上（僞碼）：

set a max to "" 
loop through sequences 
    if new sequence is bigger the max, then replace max 

找到序列可以是更有效的，如果你只步驟雖然輸入的字符，一旦。

這裏就是這樣一個版本：

def longest_substring(s1): 
    max_index, max_len = 0, 0 # keep track of the longest sequence here 
    last_c = s1[0] # previous char 
    start, seq_len = 0, 1 # tracking current seqence 

    for i, c in enumerate(s1[1:]): 
     if c >= last_c: # can we extend sequence in alpha order 
      seq_len += 1 
      if seq_len > max_len: # found longer 
       max_index, max_len = start, seq_len 
     else: # this char starts new sequence 
      seq_len = 0 
      start = i + 1 
     last_c = c 
    return s1[max_index:max_index+max_len]