LeetCode — 28. Найти индекс первого вхождения в строку
Ссылка на проблему: 28. Find the Index of the First Occurrence in a String
Даны две строки needle
и haystack
, верните индекс первого вхождения needle
в haystack
или -1, если haystack
не
содержит needle
.
Кстати, needle — иголка, haystack — стог сена.
Примеры
Пример 1:
Вход: haystack = "sadbutsad", needle = "sad"
Выход: 0
Объяснение: вхождение "sad" есть с индесом 0 и 6. Первое вхожение с нулевым индесом, поэтому возвращаем 0.
Пример 2:
Вход: haystack = "leetcode", needle = "leeto"
Выход: -1
Объяснение: строка "leetcode" не содержит "leeto", поэтому возвращаем -1.
Решение
Рассмотрим вымышленный пример, чтобы объяснить логику: haystack = "oldbutgood"
, needle = "but"
.
Длина строки needle = 3. Значит, мы можем построить цикл, в котором будем брать отрезок в 3 символа от haystack и сравнивать его с искомой строкой. Если они равны, значит это нужный индекс. Если они не равны, увеличиваем индекс и ищем дальше.
i = 0:
oldbutgood
old // haystack[0:3]
i = 1:
oldbutgood
ldb // haystack[1:4]
i = 2:
oldbutgood
dbu // haystack[2:5]
i = 3:
oldbutgood
but // haystack[3:6]
Отрезок берется как haystack[i:len(needle)+i]
.
Допустимый интервал для поиска: 0 <= i <= len(haystack) - len(needle)
. Верхняя граница такая, потому что в случае,
если len(haystack) = 10; len(needle) = 3 и i = 8: отрезок от haystack будетhaystack[8:11]
— out of range.
Если цикл завершился и совпадений не найдено — возвращаем -1
.
Решение на Go:
func strStr(haystack string, needle string) int {
for i := 0; i <= len(haystack) - len(needle); i++ {
if haystack[i:len(needle)+i] == needle {
return i
}
}
return -1
}
Пост в телеграм-канале для вопросов и обсуждения: https://t.me/labnotesru/52.