Подпоследовательность

Постановка задачи

s = "abc", t = "ahbgdc"

true

s = "axc", t = "ahbgdc"

false

Решение

Это очень простая задача - разминка, которую дают на интервью для разогрева. В ней интересно то, что паттерн двух указателей применяется не в одной структуре данных, а в разных (в двух разных строках). Задача показывает, можете ли вы обойтись без создания лишних копий строк и не спотыкаетесь ли вы в индексах.

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

Проблема с таким подходом в том, что если в строке t всего 30 символов, то количество подпоследовательностей будет 2³⁰ (больше миллиарда). Это катастрофически медленно и по памяти, и по времени.

Идея решения:

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

Первый указатель будет отслеживать текущий символ в строке s для сопоставления, а второй будет постоянно двигаться по строке t. Если под указателями оказались одинаковые символы, это означает, что мы нашли один из нужных символов подпоследовательности s и можем сдвинуть первый указатель.

Основные шаги:

1. Первый указатель i ставим в начало короткой строки s.

2. Вторым указателем j идем в цикле по строке t.

   • Если символы под указателями совпали, s[i] == t[j], значит, мы нашли нужный символ в нужном порядке.
     • Сдвигаем i.
     • Если i == s.length, значит, все символы найдены и s - это подпоследовательность t.

3. Завершение цикла:

   • Мы прошли всю строку t, но строка s оказалась пройдена не полностью, то есть мы не нашли подпоследовательность. Возвращаем false.

Вот как это работает на примере:

s = "abc", t = "ahbgdc"

1. Указатель i = 0.
2. Идем циклом по строке t.

• j = 0 (a): совпало, i стал 1.
• j = 1 (h): идем дальше.
• j = 2 (b): совпало, i стал 2.
• j = 3 (g): идем дальше.
• j = 4 (d): идем дальше.
• j = 5 (c): совпало, i стал 3.
  • i == s.length - возвращаем true.

Итог: "abc" - это подпоследовательность "ahbgdc".

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

Временная сложность

В худшем случае (когда строка s не является подпоследовательностью или ее последний символ стоит в самом конце t) нам приходится пройти по всей строке t один раз.

Таким образом, получаем временную сложность O(n), где n - длина строки t.

Пространственная сложность

Мы не создаем никаких дополнительных структур данных кроме переменных для указателей, поэтому пространственная сложность равна O(1).

Код решения

Приведем код решения.

func isSubsequence(s string, t string) bool {
    if len(s) == 0 {
        return true
    }
    i := 0
    for j := 0; j < len(t); j++ {
        if s[i] == t[j] {
            i++
            if i == len(s) {
                return true
            }
        }
    }
    return false
}

Итоги

Задача хорошо подходит для иллюстрации паттерна два указателя.

1. Основная идея. Мы сопоставляем указатели, сохраняя их относительный порядок.

2. Стратегия сдвига. Используем поэтапное однонаправленное движение указателей.

3. Граничный случай. Пустая строка всегда является подпоследовательностью.

4. Ранний выход. Как только первый указатель достиг конца, можно сразу возвращать результат.