Дано: две строки needle и haystack, вернуть индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.
Пример:
Вход: haystack= "sadbutsad", needle= "sad"
Выходные данные: 0
Пояснения: Слово "sad" встречается с индексами 0 и 6.
Первое вхождение находится на индексе 0, поэтому мы возвращаем 0.
Ограничения:
1 <= haystack.length, needle.length <= 104
haystack и needle состоят только из строчных английских символов.
Решение(Python):
1) с помощью метода find:
def strStr(haystack: str, needle: str) -> int:
t = haystack.find(needle)
return t
find(str[, start [, end]) возвращает индекс первого вхождения подстроки в строке. Если подстрока не найдена, возвращается число -1
Временная сложность: find дает нам сложность O(n)
Пространственная сложность: O(1).
2) с помощью цикла:
def strStr(haystack: str, needle: str) -> int:
if needle == haystack:
return 0
i = 0
j = len(needle)
while j <= len(haystack):
currentNeedle = haystack[i:j]
if currentNeedle == needle:
return i
i += 1
j += 1
return -1
Если needle не равна haystack, то функция инициализирует две переменные: i - начальный индекс подстроки haystack и j - конечный индекс этой подстроки. Первоначально i устанавливается в 0, а j - в длину списка needle.
Затем используем цикл, который продолжается до тех пор, пока j не станет больше длины haystack. На каждой итерации цикла функция извлекает подстроку из haystack, которая начинается с индекса i и заканчивается индексом j - 1. Эта подстрока сохраняется в переменной currentNeedle. Затем функция сравнивает currentNeedle с needle. Если они равны, то это означает, что needle является подстрокой haystack, начинающейся с индекса i. Если currentNeedle не равен needle, то функция увеличивает i и j на 1 и продолжает следующую итерацию цикла.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем две переменные O(1) + O(1) дополнительной памяти, поэтому O(1).
