python 3 : Perfect Alphabetical Order

Question

代码的目标是在字符串中找到最长的字母子字符串。

s = 'xyzbcdezzz'
longest_string = ''
current_string = ''
stringcount = 0

for n in range (len(s) - 1):
    if s[n] <= s[n+1]:
        current_string += (s[n]+s[n+1])
        stringcount += 1
        print('current string:', stringcount, current_string)


    elif s[n] > s[n+1]:
        if len(current_string) > len(longest_string) :
            longest_string = current_string
            current_string = ''
            stringcount = 0
            print('the longest string checked is:', longest_string, ', count reset')

if len(current_string) == len(longest_string):
    print (current_string, longest_string)
if len(current_string) > len(longest_string):
    print (current_string)
if len(longest_string) > len(current_string):
    print(longest_string)

当我运行这段代码时，它给出了 'abbccd' 作为最长的子字符串，而实际上它是 'abcd'。这是因为它检查字符 a，将其与序列中的下一个字符进行比较，然后将 a 添加到 b 中，得到“ab”。然后它检查 b，与 c 比较并将 bc 加在一起，然后将“bc”添加到“ab”。

为了解决这个问题，我一直在尝试让循环跳过已经按字母顺序排列的下一个字符，并在满足条件后通过增加“n”的值来检查下一个字符，但这不会似乎什么都没做。

欢迎提出建议、提示、更正和严厉批评。

编辑:看来我误导了你们中的一些人，所以我道歉。我的意思是，如果我有一个字符串，它会按字母顺序提取最长的子字符串。在 xyzbcdezzz 的情况下，它将提取 'bcdezzz'，因为这是可能的最长字母顺序子字符串，而不是 bcde。我当前代码的问题在于它提供了 bccddeezzzzz。如果我可以在第一个 if 条件为真时跳过一个循环，那么我认为它可能适用于我的代码。

Answer 1

TL;DR:编辑后的最后一段代码解决了问题

这是最长公共(public)子串问题的变体。

def longestSubstring(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

alphabets = "abcdefghijklmnopqrstuvwxyz"
s = 'jamabcdaskl'

print('longest substring:', longestSubstring(s,alphabets))

归功于 this post 的子程序。

编辑:

上面的代码似乎不适用于所有情况，所以我不得不重新设计函数。

def longestAlphaSubstring(str2):
    str1 = "abcdefghijklmnopqrstuvwxyz"
    longest = ""
    for i in range(len(str1)+1):
        if str1[:i] in str2 and len(str1[:i])>len(longest):
            longest = str1[:i]
    return longest

print(longestAlphaSubstring('jamabcdaskl'))
print(longestAlphaSubstring('asdklfjalkdfjabcdefghijklmnopqrstuvwxyzaaabcasdkfjl;kasdf'))

输出:

abcd
abcdefghijklmnopqrstuvwxyz

这是基于子字符串应该始终以 a 开头的假设。这会遍历从 'a', 'ab', 'abc', ... 到完整的字母字符串的每个可能的子字符串，然后存储检查中遇到的最长子字符串。

为了完整起见，下面是适用于任何最长公共(public)子字符串的代码:

def longestSubstring(str1, str2):
    longest = ""
    for j in range(len(str1)):
        for i in range(len(str1)+1):
            if str1[j:i] in str2 and len(str1[j:i])>len(longest):
                longest = str1[j:i]
    return longest

其中一个字符串按顺序包含字母，另一个包含测试字符串。请注意，这是 O(n^2) 的复杂度(对于小情况并不重要)。