按字母顺序查找最长的子字符串

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]