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

问题描述：

我想编写一个按字母顺序打印最长的子字符串的程序。按字母顺序查找最长的子字符串

而且在关系的情况下，它打印第一个子字符串。

这里是我写的

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))

但是，它不工作，我不知道该怎么办的第二部分。

你能帮助我吗？

'return'立即爆发的功能，所以不出意外将受到考验。只要'如果s1：'中的alpha [i：k]是'True'，'for'循环就会结束。 – roganjosh

你只想接受命令行中的一个参数吗？你想接受文件输入吗？ – 0TTT0

子字符串是否需要按顺序字母顺序排列（abcdefg）或只是按顺序（afgjkmpz）？字母顺序必须增加，还是不减少（aaaabbbbbwwxyz）？ –

答

这里是你的代码看起来应该达到你想要的东西：

#!/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))

你是正确返回该功能的第一个字母顺序排列的子串你找到。在我的代码中，我们将它们添加到列表中，然后打印出最长的一个。

答

除了建立所有可能的子串切片的列表，然后检查字符串中存在哪一个，你可以建立一个所有连续子串的列表，然后取最大长度的列表。

这很容易通过使用该角色的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)

请注意，这个（非常聪明！）分组仅适用于字符串严格按字母顺序排列的情况。我假设子字符串“aceg”也将按字母顺序考虑。 –

@AdamSmith你说得对。我添加了一个强制按字母顺序排列的版本。 –

答

假设子串包含按字母顺序排列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)

答

你重新写一个版本的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)

答

备份并再次查看此问题。 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]

开始=“2”>

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

相关推荐