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

Find the longest substring in alphabetical order

提问by spacegame

I have this code that I found on another topic, but it sorts the substring by contiguous characters and not by alphabetical order. How do I correct it for alphabetical order? It prints out lk, and I want to print ccl. Thanks

我在另一个主题上找到了这段代码，但它按连续字符而不是按字母顺序对子字符串进行排序。如何按字母顺序更正它？它打印出来lk，我想打印ccl。谢谢

ps: I'm a beginner in python

ps：我是python的初学者

s = 'cyqfjhcclkbxpbojgkar'
from itertools import count

def long_alphabet(input_string):
    maxsubstr = input_string[0:0] # empty slice (to accept subclasses of str)
    for start in range(len(input_string)): # O(n)
        for end in count(start + len(maxsubstr) + 1): # O(m)
            substr = input_string[start:end] # O(m)
            if len(set(substr)) != (end - start): # found duplicates or EOS
                break
            if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr):
                maxsubstr = substr
    return maxsubstr

bla = (long_alphabet(s))
print "Longest substring in alphabetical order is: %s" %bla

采纳答案by Tim Peters

Try changing this:

尝试改变这个：

        if len(set(substr)) != (end - start): # found duplicates or EOS
            break
        if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr):

to this:

对此：

        if len(substr) != (end - start): # found duplicates or EOS
            break
        if sorted(substr) == list(substr):

That will display cclfor your example input string. The code is simpler because you're trying to solve a simpler problem :-)

这将为ccl您的示例输入字符串显示。代码更简单，因为您正在尝试解决更简单的问题:-)

回答by solution

s = 'cyqfjhcclkbxpbojgkar'
r = ''
c = ''
for char in s:
    if (c == ''):
        c = char
    elif (c[-1] <= char):
        c += char
    elif (c[-1] > char):
        if (len(r) < len(c)):
            r = c
            c = char
        else:
            c = char
if (len(c) > len(r)):
    r = c
print(r)

回答by ejrb

You can improve your algorithm by noticing that the string can be broken into runs of ordered substrings of maximal length. Any ordered substring must be contained in one of these runs

您可以通过注意到可以将字符串分解为最大长度的有序子字符串的运行来改进算法。任何有序的子字符串必须包含在这些运行之一中

This allows you to just iterate once through the string O(n)

这允许您只迭代一次字符串 O(n)

def longest_substring(string):
    curr, subs = '', ''
    for char in string:
        if not curr or char >= curr[-1]:
            curr += char
        else:
            curr, subs = '', max(curr, subs, key=len)
    return max(curr, subs, key=len)

回答by kirancodify

In Python character comparison is easy compared to java script where the ASCII values have to be compared. According to python

与必须比较 ASCII 值的 Java 脚本相比，Python 中的字符比较很容易。根据蟒蛇

a>b gives a Boolean False and b>a gives a Boolean True

a>b 给出一个布尔值 False 并且 b>a 给出一个布尔值 True

Using this the longest sub string in alphabetical order can be found by using the following algorithm :

可以使用以下算法找到按字母顺序排列的最长子字符串：

def comp(a,b):
    if a<=b:
        return True
    else:
        return False
s = raw_input("Enter the required sting: ")
final = []
nIndex = 0
temp = []
for i in range(nIndex, len(s)-1):
    res = comp(s[i], s[i+1])
    if res == True:       
           if temp == []:
           #print i
               temp.append(s[i])
               temp.append(s[i+1])
           else:
               temp.append(s[i+1])
       final.append(temp)
        else:
       if temp == []:
        #print i
        temp.append(s[i])
       final.append(temp)
       temp = []
lengths = []
for el in final:
    lengths.append(len(el))
print lengths
print final
lngStr = ''.join(final[lengths.index(max(lengths))])
print "Longest substring in alphabetical order is: " + lngStr

回答by Andrew Winterbotham

Slightly different implementation, building up a list of all substrings in alphabetical order and returning the longest one:

稍微不同的实现，按字母顺序构建所有子字符串的列表并返回最长的一个：

def longest_substring(s):
    in_orders = ['' for i in range(len(s))]
    index = 0
    for i in range(len(s)):
        if (i == len(s) - 1 and s[i] >= s[i - 1]) or s[i] <= s[i + 1]:
            in_orders[index] += s[i]
        else:
            in_orders[index] += s[i]
            index += 1
    return max(in_orders, key=len)  

回答by jam65st

In a recursive way, you can import countfrom itertools

以递归方式，您可以从itertools导入计数

Or define a same method:

或者定义一个相同的方法：

def loops( I=0, S=1 ):
    n = I
    while True:
        yield n
        n += S

With this method, you can obtain the value of an endpoint, when you create any substring in your anallitic process.

使用此方法，当您在分析过程中创建任何子字符串时，您可以获得端点的值。

Now looks the anallize method (based on spacegameissue and Mr. Tim Petterssuggestion)

现在看 anallize 方法（基于spacegame问题和Tim Petters先生的建议）

def anallize(inStr):
    # empty slice (maxStr) to implement
    # str native methods
    # in the anallize search execution
    maxStr = inStr[0:0]
    # loop to read the input string (inStr)
    for i in range(len(inStr)):
        # loop to sort and compare each new substring
        # the loop uses the loops method of past
        # I = sum of: 
        #     (i) current read index
        #     (len(maxStr)) current answer length
        #     and 1
        for o in loops(i + len(maxStr) + 1):
            # create a new substring (newStr)
            # the substring is taked:
            # from: index of read loop (i)
            # to:   index of sort and compare loop (o)
            newStr = inStr[i:o]

            if len(newStr) != (o - i):# detect and found duplicates
                break
            if sorted(newStr) == list(newStr):# compares if sorted string is equal to listed string
                # if success, the substring of sort and compare is assigned as answer
                maxStr = newStr
    # return the string recovered as longest substring
    return maxStr

Finally, for test or execution pourposes:

最后，对于测试或执行倾注：

# for execution pourposes of the exercise:
s = "azcbobobegghakl"
print "Longest substring in alphabetical order is: " + anallize( s )

The great piece of this job started by: spacegameand attended by Mr. Tim Petters, is in the use of the native str methods and the reusability of the code.

这项工作的伟大之处在于：spacegame并由Tim Petters先生参与，在于原生 str 方法的使用和代码的可重用性。

The answer is:

答案是：

Longest substring in alphabetical order is: ccl

按字母顺序排列的最长子串是：ccl

回答by Vladimir R

Another way:

其它的办法：

s = input("Please enter a sentence: ")
count = 0
maxcount = 0
result = 0
for char in range(len(s)-1):
    if(s[char]<=s[char+1]):
       count += 1        
    if(count > maxcount):
           maxcount = count
           result = char + 1

    else:

        count = 0
startposition = result - maxcount
print("Longest substring in alphabetical order is: ", s[startposition:result+1])

回答by Rishith Poloju

s = "azcbobobegghakl"
ls = ""
for i in range(0, len(s)-1):
    b = ""
    ss = ""
    j = 2
    while j < len(s):
        ss = s[i:i+j]
        b = sorted(ss)
        str1 = ''.join(b)
        j += 1
        if str1 == ss:
            ks = ss
        else:
            break
    if len(ks) > len(ls):
        ls = ks
print("The Longest substring in alphabetical order is "+ls)

回答by prashasthbaliga

Use list and max function to reduce the code drastically.

使用 list 和 max 函数来大幅减少代码。

actual_string = 'azcbobobegghakl'
strlist = []
i = 0
while i < len(actual_string)-1:
    substr = ''
    while actial_string[i + 1] > actual_string[i] :
        substr += actual_string[i]
        i += 1
        if i > len(actual_string)-2:
            break
    substr += actual-string[i]
    i += 1
    strlist.append(subst)
print(max(strlist, key=len))

回答by user3337142

s = 'cyqfjhcclkbxpbojgkar'
longest = ""
max =""

for i in range(len(s) -1):
    if(s[i] <= s[i+1] ):
       longest = longest + s[i]
       if(i==len(s) -2):
           longest = longest + s[i+1]
    else:
        longest  = longest + s[i]        
        if(len(longest) > len(max)):
            max = longest
        longest = ""        

if(len(s) == 1):
    longest = s


if(len(longest) > len(max)):
    print("Longest substring in alphabetical order is: " + longest)
else:
    print("Longest substring in alphabetical order is: " + max)