Удаление звездочек из строки

Средняя

medium , string , stack

05 April 2024

Описание задачи #

Вам дана строка s, содержащая звездочки *.

За одну операцию вы можете:

Выбрать одну звезду в строке s
Удалить ближайший символ (не *) слева от неё, а также удалить саму звезду.

Верните строку после того, как все звезды были удалены.

Примечание

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

Ограничения #

Длина строки s находится в диапазоне от 1 до 10⁵
Строка s содержит только символы * и строчные буквы латинского алфавита
Строка гарантированно валидна

Примеры #

Входные данные: "leet**cod*e"

Ответ: "lecoe"
Входные данные: "erase*****"

Ответ: ""

Решение #

На самом деле эта задача не соответствует среднему уровню сложности и решается крайне просто.

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

если символ не равен *, то добавляем его в стек
если символ равен *, то удаляем предыдущий символ из стека

Таким образом после перебора всей строки мы получим в стеке только нужные символы. В конце остается только собрать стек в строку и вернуть ее.

Реализация #

package remove_stars

func removeStars(s string) string {
	res := make([]rune, 0, len(s))

	for _, char := range []rune(s) {
		if char == '*' {
			res = res[:len(res)-1]
		} else {
			res = append(res, char)
		}
	}

	return string(res)
}

export const removeStars = (s: string): string => {
    let res: string[] = []

    for (let char of s) {
        if (char === "*") {
            res.pop()
        } else {
            res.push(char)
        }
    }

    return res.join("")
}

Оценка сложности #

По времени

Сложность O(n), так как мы итерируемся по всей строке.

По памяти

Сложность O(n), так как мы создаем стек для хранения промежуточного результата.

Оригинал задачи на Leetcode

Algorithmics