🔴 Hard
44. Wildcard Matching

📰 Для входной строки s и шаблона p реализуйте сопоставление, где:
'?' — cоответствует любому отдельному символу;
'*' — соответствует любой последовательности символов (включая пустую последовательность);
Сопоставление должно охватывать всю входную строку (не частично)

Подсказка: запоминая позицию '*', проверяйте два случая: замена ее на пустую и заполненную последовательность

136/200
#hard
#leetcode44

✅ Решение задачи 44

Time: O(nm)
Space: O(1)

💡 Идея
▫Проходя по строке S, возможны 4 ситуации соотнесения с шаблоном P:
1⃣Символы равны или символ шаблона P равен '?' — тогда увеличиваем оба указателя
2⃣Символ шаблона равен '*' — тогда мы сохраняем его позицию и соответствующую позицию match в строке S, а затем увеличиваем позицию шаблона (то есть заменяем '*' на пустую последовательность)
3⃣Символы не равны, но при этом уже встречалась '*' — тогда мы возвращаемся к сохраненным позициям на единицу вперед и увеличиваем позицию match, то есть попадая в этот случай, мы используем '*' в качестве последовательности символов и передвигаем только позицию строки S
4⃣Символы не равны, при этом '*' не было — тогда возвращаем false
▫После выполнения цикла обрабатываем случай, если в конце шаблона P остались '*', которые можно просто заменить на пустоту
▫В результате возвращаем true, если оба указателя достигли конца строк

📎Хороший пример, чтобы разобраться с алгоритмом:

s = "abcabczzzde", p = "*abc???de*"

#solution44

🟡 Medium
64. Minimum Path Sum

📰 Для заданной матрицы найдите путь из левого верхнего угла в правый нижний с минимальной суммой всех чисел, при этом двигаясь только вниз или вправо

Подсказка: используйте динамическое программирование

137/200
#medium
#leetcode64

✅ Решение задачи 64

Time: O(nm)
Space: O(1)

💡 Идея
🟪Начиная с первого столбца, заполняем первую строку, суммируя ячейки слева, так как в них можно прийти только таким способом
🟪Следуя такой же логике, заполняем первый столбец, только теперь суммируем элементы сверху
🟪Далее заполняем минимальными путями остальные ячейки, начиная с [1,1], суммируя с текущей минимальную из левой и верхней
🟪В результате в правой нижней ячейке получаем путь с минимальной суммой

#solution64

🟡 Medium
454. 4Sum II

📰 Даны четыре целочисленных массива, все имеют длину n, вернуть количество четверок индексов (i, j, k, l), таких что:
▫ 0 <= i, j, k, l < n
▫ nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Подсказка: используйте HashMap

138/200
#medium
#leetcode454

✅ Решение задачи 454

Time: O(n²)
Space: O(n²)

💡 Идея
🟦Составляем HashMap из первых двух массивов, где ключом будет являться сумма отдельных элементов, а значением количество таких сумм
🟦Далее проходимся по оставшимся двум массивам и ищем в HashMap сумму, обратную num3 + num4, чтобы получить на выходе 0, и складываем в результат ее количество
🟦В итоге, в ответ просуммированы все варианты четверок элементов, сумма которых равна 0

#solution454

🟡 Medium
189. Rotate Array

📰 Дан целочисленный массив, поверните его вправо на k шагов, где k— неотрицательное число

Попробуйте реализовать решение, используя O(1) памяти

Подсказка: перед перестановкой элементов переверните части массива, разделенные k

139/200
#medium
#leetcode189

✅ Решение задачи 189

Time: O(n)
Space: O(1)

💡 Идея
🟪Предварительно реализуем функцию reverse, которая будет переворачивать часть массива по заданным границам
🟪В начале исключим вариант, что k больше n (длина массива), взяв для него остаток от деления на n
🟪Далее переворачиваем поочередно части массива, разделенные k:
▫ от 0 до n - k - 1, то есть первую часть массива
▫ от n - k до n - 1 — вторую часть массива
🟪Затем переворачиваем весь массив и получаем ответ

#solution189

🟡 Medium
209. Minimum Size Subarray Sum

📰 Дан массив положительных целых чисел и положительное целое число target, вернуть минимальную длину подмассива, сумма которого больше или равна target

Подсказка: используйте подход sliding window

140/200
#medium
#leetcode209

✅ Решение задачи 209

Time: O(n)
Space: O(1)

💡 Идея
🟪Используем подход с использованием скользящего окна, для этого:
▫Проходим по массиву и считаем текущую сумму
▫Если она превысила или равна target — сравниваем размер окна с текущим минимальным результатом
▫Затем передвигаем левый указатель вперед, пока сумма не станет меньше target, вычитая элементы находящиеся под ним
🟪В результате получаем минимальную длину подмассива с суммой большей или равной target

#solution209

🟡 Medium
394. Decode String

📰 Дана закодированная строка, вернуть ее декодированную.

Правило кодирования: k[string], где string внутри квадратных скобок повторяется ровно k раз, где k — гарантированно положительное целое число. Входная строка всегда соответствует данному формату.

Подсказка: используйте два стека — для чисел и символов, чтобы обрабатывать варианты вложенностей

141/200
#medium
#leetcode394

✅ Решение задачи 394

Time: O(n)
Space: O(n)

💡 Идея
🟦Проходя по заданной строке, есть 4 варианта обработки символа:
1⃣Цифра — запоминаем ее в переменной n, при этом учитываем вариант, что число k может иметь больше одного знака (n = n * 10 + (c - '0'))
2⃣Буква — добавляем символ в текущую строку
3⃣'[' — кладем в стек текущую строку из символов и число n, а затем обнуляем данные переменные, для того, чтобы учесть варианты вложенностей
4⃣']' — запоминаем текущую строку в переменной temp и из стеков достаем значение числа повторений и сохраненную строку, присваивая её текущей строке, а затем добавляем к ней temp n раз
🟦В результате получаем полностью декодированную строку с учетом всех вложенностей

#solution394

🟡 Medium
38. Count and Say

📰 Дано положительное целое число n, вернуть последовательность «подсчитай и скажи».
Последовательность «подсчитай и скажи» представляет собой последовательность цифр, определяемую рекурсивной формулой:
▫countAndSay(1) — "1"
▫countAndSay(n) — представляет собой кодирование RLE серий countAndSay(n - 1).
RLE — это метод сжатия строк, который работает путем замены последовательных одинаковых символов на конкатенацию символа и числа, обозначающего количество символов.

Например, чтобы сжать строку "3322251", мы заменяем "33"на "23", "222"на "32", "5"на "15" и "1"на "11". Таким образом, сжатая строка становится "23321511"

Подсказка: рекурсивно дойдите до базового случая, а затем с помощью цикла реализуйте логику кодирования

142/200
#medium
#leetcode38

✅ Решение задачи 38

Time: O(2^n)
Space: O(n)

💡 Идея
🟪Рекурсивно доходим до базового случая, получая строку s = "1"
🟪Затем преобразуем каждый вариант строки из стека рекурсии, проходя по ней следующим образом:
▫увеличиваем счетчик символов
▫если символ последний в строке или он не равен следующему — добавляем счетчик и данный символ в текущее преобразование строки
🟪Таким образом, с помощью рекурсии мы каждый раз получаем текущий вариант кодирования строки от 1 до n, пока не получим итоговый ответ

#solution38

🟡Medium
713. Subarray Product Less Than K

📝 Дан массив целых чисел и целое число k, вернуть количество подмассивов, где произведение всех элементов строго меньше k

💡: используйте подход sliding window

143/200
#leetcode713 | #medium

✅ Решение задачи 713

Time: O(n)
Space: O(1)

⚡️ Идея
▫Используем подход sliding window, для этого:
➖проходим по массиву и считаем текущее произведение
➖если оно превысило или равно k — передвигаем левый указатель вперед, деля произведение на элементы находящиеся под ним, пока оно не станет меньше k
➖добавляем в результат текущий размер окна
▫В результате получаем количество подмассивов, где произведение всех элементов строго меньше k

#solution713

🟡Medium
583. Delete Operation for Two Strings

📝 Даны две строки, вернуть минимальное количество шагов для получения одинаковых строк.
За один шаг вы можете удалить ровно один символ в любой строке

💡: найдите длину самой длинной общей подпоследовательности

144/200
#leetcode583 | #medium

✅ Решение задачи 583

Time: O(nm)
Space: O(nm)

⚡️ Идея
▫реализуем функцию, которая будет находить длину самой длинной общей подпоследовательности двух строк (объяснение здесь)
▫после этого остается только вычесть из каждой строки найденную длину, чтобы получить количество тех символов, которые необходимо удалить для получения одинаковых строк

#solution583

🟡 Medium
279. Perfect Squares

📝Дано целое число n, вернуть наименьшее количество полных квадратов чисел, сумма которых равна n

💡: используйте динамическое программирование

145/200
#leetcode279 | #medium

✅ Решение задачи 279

Time: O(√nn)
Space: O(n)

⚡️ Идея
▫используем динамическое программирование, перебирая все числа от 1 до n и последовательно вычисляя dp[i]:
➖изначально для каждого i присваиваем значение n, как максимально возможный случай
➖далее вложенным циклом перебираем все квадраты j от 1 до i и для каждого выбираем минимальное значение между текущим dp[i] и dp[i - j²] + 1
▫в результате в dp[n] получаем ответ

#solution279

🔴Hard
32. Longest Valid Parentheses

📝 Для данной строки, содержащей только символы '(' и ')', вернуть длину самой длинной допустимой подстроки

💡: используйте стек с индексами открывающих скобок

146/200
#leetcode32 | #hard