Использование вложенного цикла for и оператора if для замены символа на целое

Question

Мне нужно вывести любой повторяющийся символ для ссылки на предыдущий символ.

Например: a(-1)rdv(-4)(-4)k или hel(-1)o

Это мой код:

text= 'aardvark'
i=0
j=0
for i in range(len(text)-1):
    for j in range(i+1, len(text)):
        if text[j]==text[i]:
            sub= text[j]
            val2=text.find(sub, i+1, len(text))
            p=val2+1
            val=str(i-j)
            text= text[:val2] + val + text[p:] 
            break
print(text)

Вывод: a-1rdva-4k

второй 'a' не распознан.И я не уверен, как включить скобки в мою печать.

Answer 1

text= 'aardvark'
d={}  # create a dictionary to keep track of index of element last seen at
new_text=''  # new text to be generated
for i in range(len(text)):  # iterate in text from index 0 up to length of text
    c = text[i]  # storing a character in temporary element as used frequently 
    if c not in d:  # check if character which is explored is visited before or not
        d[c] = i  # if character visited first time then just add index value of it in dictionary
        new_text += c  # concatenate character to result text
    else:  # visiting alreaady visited character
        new_text += '({0})'.format(d[c]-i)  # used string formatting which will print value of difference of last seen repeated character with current index instead of {0}
        d[c] = i  # change last seen character index
print(new_text)

Выход:

a(-1)rdv(-4)(-4)k

Answer 2

Обновляя текст на месте каждый раз, когда вы находите обратную ссылку, вы портите свои индексы (ваш текст каждый раз становится длиннее), и вы никогда не обрабатываете последние символы должным образом. Вы останавливаете проверку, когда обнаруживаете первое повторение «текущего» символа, поэтому третий a никогда не обрабатывается. Это относится к каждому 3-му повторению во входной строке. Кроме того, если ваш входной текст содержит какие-либо - символы или цифры, они в конечном итоге будут проверены на соответствие ссылкам -offset, которые вы вставили перед ними!

Для вашего конкретного примера aardvark, строки с 8 символами, что происходит так:

• Вы найдете второй a и установите text на a-1rdvark. Текст теперь имеет длину 9 символов, поэтому последний символ r никогда не будет проверяться (вы не больше i = 6); это было бы проблемой, если бы ваша тестовая строка заканчивалась двойной буквой. Вы выходите из цикла, поэтому цикл j for никогда не дойдет до 3-го a, и второй a больше не может быть проверен, так как он уже заменен.

• Ваш код находит - (не повторяется), 1 (не повторяется) и затем r (повторяется один раз), так что теперь вы заменяете text на a-1rdva-4k. Теперь у вас есть строка из 10 символов, поэтому - и 4 никогда не будут проверяться. Больше не проблема, но что, если было повторение только в последних 3 позициях строки?

Создание нового объекта для вывода (с добавлением как букв, которые вы не видели раньше, так и обратных ссылок). Таким образом, вы не будете вызывать рост текста, который зацикливаете, и продолжите находить повторы; для круглых скобок вы можете использовать больше конкатенации строк. Вам нужно будет отсканировать часть строки до i, а не после, чтобы это сработало, и вернуться назад! Тестирование i - 1, i - 2 и т. Д. До 0. Естественно, это означает, что ваша петля i должна быть в диапазоне до полной длины:

output = ''

for i in range(len(text)):
    current = text[i]
    for j in range(i - 1, -1, -1):
        if text[j] == current:
            current = '(' + str(j - i) + ')'
            break  
    output = output + current

print(output)

Я сохранил это исправление до минимума, но в идеале я бы также внес еще некоторые изменения:

• Добавьте все обработанные символы и ссылки в новый список вместо строки, а затем используйте str.join(), чтобы впоследствии присоединить этот список к выводу. Это гораздо эффективнее, чем перестраивать строку на каждой итерации.

• Использование двух циклов означает, что вы проверяете каждый символ в строке снова, пока зацикливаетесь на тексте, поэтому количество шагов, которые алгоритм выполняет, увеличивается экспоненциально с длиной входного сигнала. В области компьютерных наук мы говорим о временной сложности алгоритмов, и у вас есть алгоритм O (N ^ 2) (N в квадрате) экспоненциальный . Текст с 1000 букв может занять до 1 миллиона шагов! Вместо циклического экспоненциального числа раз вы можете использовать словарь для отслеживания индексов букв, которые вы видели. Если в словаре есть символ current , вы можете просто вычислить смещение. Поиск в словаре занимает постоянное время (O (1)), поэтому весь алгоритм занимает линейное время (O (N)), что означает, что время, затрачиваемое процессом, прямо пропорционально длине входной строки.

• Используйте enumerate(), чтобы добавить счетчик в цикл, чтобы вы могли просто циклически перебирать символы, не нужно использовать range().

• Вы можете использовать форматирование строки для построения "(<offset>)" строки; Python 3.6 и новее имеют строковые литералы в формате , где f'...' строки принимают {} заполнителей, которые являются просто выражениями. f'({some - calculation + or * other})' will execute the expression and put the result in a string that has (and) characters in it too. For earlier Python versions, you can use the [ str.format () method](https://docs.python.org/3/library/stdtypes.html#str.format) to get the same result; the syntax then becomes '({})'. Формат (некоторые - расчет + или * другие) `.

Соедините, это станет:

def add_backrefs(text):
    output = []
    seen = {}
    for i, character in enumerate(text):
        if character in seen:
            # add a back-reference, we have seen this already
            output.append(f'({seen[character] - i})')
        else:
            # add the literal character instead
            output.append(character)
        # record the position of this character for later reference
        seen[character] = i
    return ''.join(output)

Демо-версия:

>>> add_backrefs('aardvark')
'a(-1)rdv(-4)(-4)k'
>>> add_backrefs('hello')
'hel(-1)o'