Python 3:完美的字母顺序

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.如果我可以在第一个条件为真时跳过一个循环,那么我认为它可能在我的代码中有效.

Answer 1

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

这是最长公共子串问题的变体.

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

这个帖子的子程序的功劳.

编辑:

看起来上面的代码并不适用于所有情况,因此我不得不重新设计该函数.

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',...到每个可能的子字符串,直到完整的字母串,然后存储检查中遇到的最长子字符串.

为了完整起见,这里的代码适用于任何最长的公共子字符串:

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)的复杂性(对于小的情况不重要).

Answer 2

循环的不同版本zip(strg, strg[1:]),以便比较同一循环迭代中的先前和当前字符:

def longest_substring(strg):

    substring = strg[0]
    max_substring = ''

    for cur, nxt in zip(strg, strg[1:]):

        if ord(nxt) >= ord(cur):
            substring += nxt
            if len(substring) > len(max_substring):
                max_substring = substring
        else:
            substring = nxt

    return max_substring

用ord这种方式比较字符的缺点是这些字符!"#$%&'()*+,-./0123456789:;=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_``abcdefghijklmnopqrstuvwxyz{|}~将被视为"按字母顺序".你可能需要根据自己的需要进行调整......

Answer 3

从算法的角度来看,最优化的方法是使用后缀树来查找给定字符串中最长的子字符串.(我刚才在python中实现了后缀树的优化版本.如果你有兴趣可以查看https://github.com/kasramvd/SuffixTree

作为另一种hacky方式,您可以利用Numpy来查找最大的子字符串diff(),where()并使用以下split()函数:

In [52]: s = 'pqsrjamabcdaskl'

In [54]: ''.join(max(np.split(list(s), np.where((np.diff([ord(i) for i in s]) == 1) == False)[0] + 1), key=len))
Out[54]: 'abcd'

说明:

这段代码背后的逻辑是找到ascii值为1的字符的索引.

在numpy,我们可以通过np.diff功能简单地做到这一点.但由于它需要一组项目,我们可以使用列表推导将预期值列表传递给函数.然后通过将结果与1进行比较,我们可以得到一个bool数组列表,如下所示:

In [55]: np.diff([ord(i) for i in s]) == 1           
Out[55]: 
array([ True, False, False, False, False, False, False,  True,  True,
        True, False, False, False,  True], dtype=bool)

现在我们可以使用False项的索引np.where将它们传递给split函数:

In [57]: np.split(list(s), np.where((np.diff([ord(i) for i in s]) == 1) == False)[0] + 1)
Out[57]: 
[array(['p', 'q'], 
       dtype='<U1'), array(['s'], 
       dtype='<U1'), array(['r'], 
       dtype='<U1'), array(['j'], 
       dtype='<U1'), array(['a'], 
       dtype='<U1'), array(['m'], 
       dtype='<U1'), array(['a', 'b', 'c', 'd'], 
       dtype='<U1'), array(['a'], 
       dtype='<U1'), array(['s'], 
       dtype='<U1'), array(['k', 'l'], 
       dtype='<U1')]

这+1实际上是因为np.split从0分裂到我们的第一个索引,然后从第一个索引分割到下一个索引等等.

最后,max通过传递len关键函数,我们可以使用函数获得最长的数组.

另外请注意,这种做法会给你时间最长的连续序列,如果你只在乎你可以替换的顺序== 1用> 0.这是一个例子:

In [13]: s = 'pqsrjamabcdasklptvxz'

In [14]: ''.join(max(np.split(list(s), np.where((np.diff([ord(i) for i in s]) > 0) == False)[0] + 1), key=len))
Out[14]: 'klptvxz'

Answer 4

编辑后，您的问题是什么就更清楚了。我尽可能少地修改了您的代码，以向您展示解决方案中的错误来自何处。

这是代码：

s = 'xyzbcdezzz'
longest_string = ''
current_string = ''

for n in range(len(s)):
    if len(current_string) == 0 or current_string[-1] <= s[n]:
        current_string += s[n]
        print('current string:', len(current_string), current_string)
    else:
        if len(current_string) > len(longest_string):
            longest_string = current_string
        current_string = s[n]
        print('the longest string checked is:', longest_string, ', count reset')

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

print(longest_string)

有问题的部分是一次占用 2 个字符

if s[n] <= s[n+1]:
    current_string += (s[n]+s[n+1])

将其替换为

if len(current_string) == 0 or current_string[-1] <= s[n]:
        current_string += s[n]

如果添加有效，您将准确地添加到当前字符串（最后一个字符current_string[-1]和添加的想要的字符s[n]按顺序排列）

elif 部分被简化为不检查s[n]，s[n+1]因为它不反映我们想要做的事情：我们不关心字符在整个字符串中是否按顺序排列，s我们关心我们当前的字符串（此逻辑由 if 捕获）上面的语句，只有出现问题才会访问else）

所以这里的改变是

elif s[n] > s[n+1]:
    if len(current_string) > len(longest_string) :

到

else:
    if len(current_string) > len(longest_string):
        longest_string = current_string
    current_string = s[n]

如有必要，添加新的获胜者并将当前字符串重置为不按顺序的字符

current_string最后一组 ifs 正在检查在最后一个字符结束时的情况s，虽然这是正确的，但如果您在循环后添加一个检查并仅打印最长的字符串，则不会那么分散注意力

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

这样，在每种情况下，输出都是第一个有效的最长字符串，而不是当其中一个位于字符串尾部时，输出两个不同的最长字符串