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

Question

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

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

score 15 · Accepted Answer

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)

score 5 · Accepted Answer

尝试改变这个：

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

对此：

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

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

score 4 · Accepted Answer

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

这允许您只遍历字符串 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)

score 3 · Accepted Answer

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)

score 2 · Accepted Answer

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

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

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

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

现在看 anallize 方法（基于spacegame issue 和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

最后，对于测试或执行来说：

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

这项工作的伟大部分始于：spacegame ，由Tim Petters先生参与，在于使用本机 str 方法和代码的可重用性。

答案是：

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

score 1 · Accepted Answer

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

a>b 给出布尔值 False，b>a 给出布尔值 True

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

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

哇，这里有一些非常令人印象深刻的代码片段......我想添加我的解决方案，因为我认为它很干净：

s = 'cyqfjhcclkbxpbojgkar'

res = ''
tmp = ''

for i in range(len(s)):
    tmp += s[i]
    if len(tmp) > len(res):
        res = tmp
    if i > len(s)-2:
        break
    if s[i] > s[i+1]:
        tmp = ''

print("Longest substring in alphabetical order is: {}".format(res))

score 1 · Accepted Answer

不使用库，而是使用ord()返回字符的 ascii 值的函数。假设：输入为小写，不使用特殊字符

s = 'azcbobobegghakl'

longest = ''

for i in range(len(s)):
    temp_longest=s[i]

    for j in range(i+1,len(s)):

        if ord(s[i])<=ord(s[j]):
            temp_longest+=s[j]
            i+=1
        else:
            break

    if len(temp_longest)>len(longest):
        longest = temp_longest

print(longest)

score 0 · Accepted Answer

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

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)

score 0 · Accepted Answer

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)

score 0 · Accepted Answer

这对我有用

s = 'cyqfjhcclkbxpbojgkar'

lstring = s[0]
slen = 1

for i in range(len(s)):
    for j in range(i,len(s)-1):
            if s[j+1] >= s[j]:
                    if (j+1)-i+1 > slen:
                        lstring = s[i:(j+1)+1]
                        slen = (j+1)-i+1
            else:
                        break

print("Longest substring in alphabetical order is: " + lstring)

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

score 0 · Accepted Answer

input_str = "cyqfjhcclkbxpbojgkar"
length = len(input_str) # length of the input string
iter = 0
result_str = '' # contains latest processed sub string
longest = '' # contains longest sub string alphabetic order 
while length > 1: # loop till all char processed from string
    count = 1
    key = input_str[iter] #set last checked char as key 
    result_str += key # start of the new sub string
    for i in range(iter+1, len(input_str)): # discard processed char to set new range
      length -= 1
      if(key <= input_str[i]): # check the char is in alphabetic order 
        key = input_str[i]
        result_str += key # concatenate the char to result_str
        count += 1
      else:
        if(len(longest) < len(result_str)): # check result and longest str length
          longest = result_str # if yes set longest to result
        result_str = '' # re initiate result_str for new sub string
        iter += count # update iter value to point the index of last processed char
        break

    if length is 1: # check for the last iteration of while loop
        if(len(longest) < len(result_str)):
          longest = result_str

print(longest);

score 0 · Accepted Answer

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

在 python 外壳中'a' < 'b' or 'a' <= 'a' is True

result = ''
temp = ''
for char in s:
    if (not temp or temp[-1] <= char):
        temp += char
    elif (temp[-1] > char):
        if (len(result) < len(temp)):
            result = temp
        temp = char
    
if (len(temp) > len(result)):
    result = temp
    
print('Longest substring in alphabetical order is:', result)

score 0 · Accepted Answer

s=input()
temp=s[0]
output=s[0]
for i in range(len(s)-1):
    if s[i]<=s[i+1]:
        temp=temp+s[i+1]
        if len(temp)>len(output):
            output=temp           
    else:
        temp=s[i+1]

print('Longest substring in alphabetic order is:' + output)

score 0 · Accepted Answer

我对在线 EDX 的一项测试有类似的问题。花了 20 分钟集思广益，找不到解决方案。但我得到了答案。这很简单。阻止我使用其他解决方案的事情 - 光标不应该停止或具有唯一值所以说如果我们有 edx 字符串 s = 'azcbobobegghakl' 它应该输出 - 'beggh' 而不是 'begh'（唯一集）或 'kl '（根据与字母字符串最长的相同）。这是我的答案，它有效

n=0
for i in range(1,len(s)):
    if s[n:i]==''.join(sorted(s[n:i])):
        longest_try=s[n:i]
    else:
        n+=1

score 0 · Accepted Answer

在某些情况下，输入是混合字符，如“Hello”或“HelloWorld”

**条件1：**顺序判断不区分大小写，即字符串“Ab”被认为是按字母顺序排列的。

**条件2：**您可以假设输入不会有一个字符串，其中按字母顺序排列的可能连续子字符串的数量为0。即输入不会有像“zxec”这样的字符串。

   string ="HelloWorld"
    s=string.lower()
    r = ''
    c = ''
    last=''
    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
    for i in r:
        if i in string:
            last=last+i
        else:
            last=last+i.upper()
    if len(r)==1:
        print(0)
    else:
        print(last)

出：黄

score 0 · Accepted Answer

```python
s = "cyqfjhcclkbxpbojgkar"  # change this to any word
word, temp = "", s[0]  # temp = s[0] for fence post problem
for i in range(1, len(s)):  # starting from 1 not zero because we already add first char
    x = temp[-1]  # last word in var temp
    y = s[i]  # index in for-loop
    if x <= y:
        temp += s[i]
    elif x > y:
        if len(temp) > len(word):  #storing longest substring so we can use temp for make another substring
            word = temp
        temp = s[i]  #reseting var temp with last char in loop
    if len(temp) > len(word):
        word = temp
print("Longest substring in alphabetical order is:", word)
```

我的代码目前将最长的子字符串存储在变量 temp 中，然后将 for 循环中的每个字符串索引与 temp (temp[-1]) 中的最后一个字符进行比较，如果索引更高或与 (temp[-1]) 相同，然后添加该字符从温度索引。如果索引低于 (temp[-1]) 检查变量 word 和 temp 哪个具有最长的子字符串，然后重置变量 temp 以便我们可以创建另一个子字符串，直到字符串中的最后一个字符。

score 0 · Accepted Answer

s = 'cyqfjhcclkbxpbojgkar'
long_sub = '' #longest substring
temp = '' # temporarily hold current substr
if len(s) == 1: # if only one character
    long_sub = s
else:
    for i in range(len(s) - 1):
        index = i
        temp = s[index]
        while index < len(s) - 1: 
            if s[index] <= s[index + 1]:
                temp += s[index + 1]
            else:
                break
            index += 1
        if len(temp) > len(long_sub):
            long_sub = temp
        temp = ''
print(long_sub)

score -2 · Accepted Answer

其他方式：

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

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

20 回答 20

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

Related

Reference