Подтвердить что ты не робот

Найти самую длинную подстроку в алфавитном порядке

У меня есть этот код, который я нашел в другой теме, но он сортирует подстроку смежными символами, а не в алфавитном порядке. Как исправить его в алфавитном порядке? Он печатает 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
4b9b3361

ОТВЕТЫ

Ответ 1

Попробуйте изменить это:

        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 для строки ввода вашего примера. Код проще, потому что вы пытаетесь решить более простую задачу: -)

Ответ 2

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)

Ответ 3

Вы можете улучшить свой алгоритм, заметив, что строка может быть разбита на прогоны упорядоченных подстрок максимальной длины. Любая упорядоченная подстрока должна содержаться в одном из этих прогонов

Это позволяет вам просто перебирать один раз через строку 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)

Ответ 4

Рекурсивным способом вы можете импортировать count из itertools

Или определите один и тот же метод:

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

С помощью этого метода вы можете получить значение конечной точки, когда вы создаете какую-либо подстроку в своем аллитическом процессе.

Теперь выглядит метод anallize (на основе spacegame и г-н предложение Тима Петтера)

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 и присутствовал г-н Тим Петтерс, используется в методах нативной str и повторном использовании кода.

Ответ:

Самая длинная подстрока в алфавитном порядке: ccl

Ответ 5

В сравнении с Python сравнение легко по сравнению с java script, где значения ASCII должны сравниваться. Согласно python

a > b дает Boolean False, а b > a дает булевую истину

Используя это, самая длинная подстрока в алфавитном порядке может быть найдена с использованием следующего алгоритма:

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

Ответ 6

Используйте список и функцию 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))

Ответ 7

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)

Ответ 8

Немного различная реализация, создающая список всех подстрок в алфавитном порядке и возвращающий самый длинный:

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)

Ответ 9

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)

Ответ 10

Это сработало для меня

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

Ответ 11

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

Ответ 12

Вау, некоторые действительно впечатляющие фрагменты кода здесь... Я хочу добавить свое решение, так как я думаю, что оно довольно чистое:

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

Ответ 13

Без использования библиотеки, но с использованием функции 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)

Ответ 14

найти самую длинную подстроку в алфавитном порядке в 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)

Ответ 15

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)

Ответ 16

Другой способ:

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