Является ли строка подпоследовательностью

Легкая

easy , string , two pointers

09 April 2024

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

Дано две строки s и t. Напишите функцию, которая возвращает true, если s является подпоследовательностью t, или false в противном случае.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения остальных символов. (т. е. ace является подпоследовательностью abcde, а aec — нет).

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

Длина строки s находится в диапазоне от 0 до 100
Длина строки t находится в диапазоне от 0 до 10000
В строках могут присутствовать только латинские буквы в нижнем регистре

Примеры #

Входные данные: s = "abc", t = "ahbgdc"

Ответ: true
Входные данные: s = "axc", t = "ahbgdc"

Ответ: false

Решение #

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

Мы запускаем цикл по всем символам строки t и сравниваем их с символами строки s. Для отслеживания позиции в строке s мы будем использовать указатель pos.

Если символы совпадают, мы двигаем указатель строки pos на одну позицию вперед.
Если после прохода по всем символам строки t указатель pos указывает на конец строки s, значит строка s является подпоследовательностью строки t.
Если во время очередной итерации выполняется это же условие, то мы моем досрочно завершить выполнение функции и вернуть true, так как дальнейший проход по строке t не имеет смысла.

Реализация #

package is_subsequence

func isSubsequence(s string, t string) bool {
	pos := 0
	runes := []rune(s)

	if s == "" {
		return true
	}

	for _, char := range []rune(t) {
		if pos == len(s) {
			return true
		}

		if char == runes[pos] {
			pos++
		}
	}

	return pos == len(s)
}

export const isSubsequence = (s: string, t: string): boolean => {
    let pos = 0

    if (s === "") {
        return true
    }

    for (let i = 0; i < t.length; i++) {
        const char = t[i]

        if (pos === s.length) {
            return true
        }

        if (char === s[pos]) {
            pos++
        }
    }

    return pos === s.length
}

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

По времени

O(n), где n — длина строки t.

По памяти

O(1) — так как мы используем константное количество памяти для хранения переменных.

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

Algorithmics