строка, в которой для каждого символа есть все символы, которые по алфавиту меньше, чем до него

Question

Как проверить строку, в которой для каждого символа в ней есть все символы, которые по алфавиту меньше, чем она, например, aab является правильным, а aacb - нет, потому что во втором случае мы имеем «c», но « б 'нет до этого. Также aac неверен, так как не имеет 'b' перед 'c'.

Answer 1

псевдокод. Работает для таких случаев, как abac тоже.

max = 'a' - 1  // character immediately before 'a'

for char in string
  if char > max + 1
    // bad string, stop algorithm
  end

  if char > max
    max = char
  end
end

Идея состоит в том, что нам нужно проверить только то, что символ, предшествующий текущему в алфавитном порядке, встречался раньше. Если у нас есть символ e сейчас и d ранее, то c, b и a тоже.

Answer 2

ALPHA = 'abcdefghijklmnopqrstuvwxyz'

tests = [
         'aab','abac','aabaacaabade', # First 3 tests should eval True
         'ba','aac','aabbccddf'       # Last 3 test should eval False
         ]

def CheckString(test):
    alpha_counter = 0
    while test:
        if test[0] == ALPHA[alpha_counter]:
            test = test.replace(ALPHA[alpha_counter],'')
            alpha_counter+=1
        else:
            return False
    return True

for test in tests:
    print CheckString(test)


True
True
True
False
False
False

Учитывая ваши критерии ...

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

aabaacaabade

возьмем приведенную выше строку, например.

first letter 'a' passes criteria    [there are no letters before 'a']
remove all 'a's from string         remaining string: bcbde

first letter 'b' passes criteria    [there was an 'a' before the 'b']
remove all 'b's from string         remaining string: cde

first letter 'c' passes criteria    [there was an 'a' and a 'b' before the 'c']
remove all 'c's from string         remaining string: de

...

Это должно сработать, если я правильно понял ваши критерии.

Answer 3

Считайте это плохим ответом

import string

foo = string.printable[10:36]
a = 'aac'


for i in a:
    if i =='a':continue
    if a.rfind(foo[foo.rfind(i)-1])!=-1:continue
    else:print 'check_not cleared';break

Answer 4

Как насчет этого? Это упрощает задачу, сначала удаляя повторяющиеся символы, затем вам нужно только проверить, является ли строка префиксом строки, содержащей все строчные (ascii) буквы.

import string

def uniq(s):
    last = None
    for c in s:
        if c != last: yield c
        last = c

def is_gapless_ascending(s):
    s = ''.join(uniq(s))
    return string.ascii_lowercase.startswith(s)

Answer 5

Идея очень проста: для каждого символа в строке он должен быть не меньше, чем предыдущий, и не должен быть больше, чем его предыдущий + 1.

Answer 6

Я считаю, что правильно понимаю ваш вопрос, и вот моя попытка ответить на него, если я неправильно понял, пожалуйста, поправьте меня.

Стандартные сравнения (<, <=,>,> =,==,! =) применяется к строкам.В этих сравнениях используются стандартные посимвольные правила сравнения для ASCII или Unicode.При этом операторы с большими и меньшими значениями будут сравнивать строки в алфавитном порядке.

Answer 7

Возможно, вы захотите использовать ascii кодировку символа.

mystr = "aab"
curr = ord(mystr[0])
for char in mystr[1:]:
    if ord(char) < curr:
        print "This character should not be here"
    if ord(char) > curr:
        curr = ord(char)

Изменения сделаны с учетом предложения пользователя 470379:

mystr = "aab"
curr = mystr[0]
for char in mystr[1:]:
    if char < curr:
        print "This character should not be here"
    if char > curr:
        curr = char