Эмуляция действия клавиши Backspace в строке

Условие

Напишите функцию backspace(text: str) -> str, которая принимает строку, где символ '' рассматривается как нажатие клавиши Backspace, удаляющее непосредственно предшествующий ему символ. Функция должна вернуть строку, из которой удалены все символы '', а также символы, стираемые ими.

def backspace(text: str) -> str:
    ...
    
assert backspace('11111*22222******33*') == '111'
assert backspace('1*289***89fhdf9812heo13*278**') == '89fhdf9812heo1'

Ответ

Используйте стек символов: обычный символ добавляйте, на * удаляйте последний, если он есть. Оба ожидаемых результата в условии ошибочны.

def backspace(text):
    result = []
    for char in text:
        if char == '*':
            if result:
                result.pop()
        else:
            result.append(char)
    return ''.join(result)

По описанному правилу правильные проверки такие:

assert backspace('11111*22222******33*') == '1113'
assert backspace('1*289***89fhdf9812heo13*278**') == '89fhdf9812heo12'

В первом случае последняя звёздочка удаляет только одну из двух троек. Во втором две последние звёздочки удаляют 8 и 7, оставляя 2. Звёздочка при пустом стеке ничего не делает. Время и память — O(n).