Введение
Условие задачи:
Даны две строки: haystack («стог сена») и needle («иголка»).
Верните индекс первого вхождения needle в haystack.
Если needle не найдена — верните -1.
Если needle — пустая строка, верните 0 (по соглашению, как в Java и Python).
Примеры: haystack = "sadbutsad", needle = "sad" → 0
haystack = "leetcode", needle = "leeto" → -1
haystack = "hello", needle = "" → 0
Объяснение для пятилетнего
Представь, что у тебя есть огромная коробка с буквами, выложенными в ряд:
H - E - L - L - O - W - O - R - L - D
А у тебя в руках — маленькая карточка с надписью: "WORLD"
Ты начинаешь слева направо и ищешь:
— Ага! Здесь начинается W… а потом O, R, L, D?
Если да — ты кричишь: «Нашёл! Она начинается на 6-й букве!» 🎉
Если не нашёл — говоришь: «Нету такой карточки тут»
Вот и всё! Ты просто ищешь маленькое слово внутри большого.
Анализ задачи
Это классическая задача поиска подстроки.
Хотя в реальной жизни мы бы просто написали haystack.indexOf(needle), на LeetCode от нас ждут собственную реализацию — без встроенных функций.
Ограничения:
- Нельзя использовать String.indexOf(), contains(), регулярные выражения и т.п.
- Нужно обработать крайние случаи: needle пустая → вернуть 0
needle длиннее haystack → вернуть -1
Подход: Brute Force (наивный перебор)
- Проходим по каждому возможному стартовому индексу в haystack.
- На каждом индексе i проверяем, совпадает ли подстрока haystack[i ... i + len(needle) - 1] с needle.
- Если совпадает — возвращаем i.
- Если дошли до конца — возвращаем -1.
Этот подход работает за O(n × m) в худшем случае (где n = haystack.length, m = needle.length), но для большинства тестов на LeetCode — достаточно.
Решение на Java (с комментариями)
Как это работает на примере?
Пример:
haystack = "hello", needle = "ll"
- n = 5, m = 2 → i идёт от 0 до 3 (5 - 2 = 3)
- i = 0: 'h' != 'l' → пропуск
- i = 1: 'e' != 'l' → пропуск
- i = 2: haystack[2] = 'l' == needle[0]
haystack[3] = 'l' == needle[1] → совпадение!
→ Возвращаем 2
Заключение
Пример, рассмотренный в статье, можно найти по адресу: