Перейти к основному содержимому

LeetCode — 28. Найти индекс первого вхождения в строку

· 2 мин. чтения
Азат Хасанов
Азат Хасанов
Автор

Ссылка на проблему: 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.