Python | LeetCode

#Hard Задача: 126.Word Ladder II Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия: Каждая пара соседних слов отличается ровно одной буквой. Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList. sk == endWord. Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk]. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

👨‍💻 Алгоритм: 1️⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS). 2️⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList. 3️⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths. 😎 Решение:

class Solution:
    def __init__(self):
        self.adjList = {}
        self.currPath = []
        self.shortestPaths = []

    def findNeighbors(self, word, wordSet):
        neighbors = []
        charList = list(word)
        for i in range(len(charList)):
            oldChar = charList[i]
            for c in "abcdefghijklmnopqrstuvwxyz":
                if c != oldChar:
                    charList[i] = c
                    newWord = "".join(charList)
                    if newWord in wordSet:
                        neighbors.append(newWord)
            charList[i] = oldChar
        return neighbors

    def backtrack(self, source, destination):
        if source == destination:
            self.shortestPaths.append(self.currPath[::-1])

        for neighbor in self.adjList.get(source, []):
            self.currPath.append(neighbor)
            self.backtrack(neighbor, destination)
            self.currPath.pop()

    def bfs(self, beginWord, endWord, wordSet):
        q = deque([beginWord])
        wordSet.discard(beginWord)
        isEnqueued = {beginWord: True}
        
        while q:
            visited = []
            for _ in range(len(q)):
                currWord = q.popleft()
                neighbors = self.findNeighbors(currWord, wordSet)
                for neighbor in neighbors:
                    if neighbor not in isEnqueued:
                        q.append(neighbor)
                        isEnqueued[neighbor] = True
                        self.adjList[neighbor] = []
                    self.adjList[neighbor].append(currWord)
                    visited.append(neighbor)
            
            for word in visited:
                wordSet.discard(word)

    def findLadders(self, beginWord, endWord, wordList):
        wordSet = set(wordList)
        self.bfs(beginWord, endWord, wordSet)
        self.currPath = [endWord]
        self.backtrack(endWord, beginWord)
        return self.shortestPaths

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Ведем набор учеников 3-10 классов на новый учебный год! Московская школа программистов - это не курсы, а школа с государственной лицензией, которая обучает детей IT с 2001 года. Мы сотрудничаем с МФТИ, НИУ ВШЭ, Яндекс и Физтехпарк Что получит ребенок, в результате обучения: - Участие и победы в олимпиадах всероссийского и международного уровня - Поступление в престижные технические вузы России и работу в известных IT-компаниях: Apple, Google, Yandex, Nvidia и других - Практику на реальных IT-проектах - Усидчивость, целеустремленность и умение работать в команде - Сдача ЕГЭ/ОГЭ на высокие баллы Сейчас идет набор в виртуальный класс. В этом формате, дети в небольших группах обучаются с преподавателем онлайн в реальном времени. Эффективно как очно. Позаботьтесь о том, чтобы ребенок стал востребованным IT-специалистом! Зарегистрироваться #реклама vc.informatics.ru О рекламодателе

#easy Задача: 125. Valid Palindrome Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры. Для данной строки s верните true, если она является палиндромом, и false в противном случае. Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

👨‍💻 Алгоритм: 1️⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода. 2️⃣Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке. 3️⃣Результирующий алгоритм прост: 1. Установите два указателя, один на каждом конце входной строки. 2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени. 3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше. 4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше. 5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине. 😎 Решение:

class Solution:
    def isPalindrome(self, s: str) -> bool:

        i, j = 0, len(s) - 1

        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1

            if s[i].lower() != s[j].lower():
                return False

            i += 1
            j -= 1

        return True

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Начните обучение в магистратуре в Центральном университете уже на 3-м курсе бакалавриата! Центральный университет — современный вуз, созданный при поддержке ведущих компаний России: Т-Банка, Авито и других. Учебу реально совместить с последними курсами бакалавриата или действующей работой. Обучение занимает 20 часов в неделю в вечернее время в первый год, а занятия проводят в центре Москвы профессоры из МГУ, МФТИ, РЭШ и практики из индустрии. Обучение в университете построено по принципам ИТ-компаний, со средой, способствующей росту и развитию. У каждого студента будет: - личный ментор по траектории обучения; - доступ к карьерному центру с коучами и консультантами; - опыт работы в проектах 30+ компаний-партнеров уже во время обучения; - диплом гособразца. Участвуйте в онлайн-отборе, чтобы выиграть грант на обучение до 1,2 млн рублей. Больше подробностей про университет и конкурс грантов по ссылке! erid:2VtzqwqkG5y Реклама, АНО ВО «Центральный университет», ИНН 7743418023

Jobski - твой помощник при поиске работы в IT Сервис индивидуально подбирает вакансии, учитывая ваш опыт, навыки и стек технологий. Узнать больше #реклама jobski.ru О рекламодателе

#hard Задача: 124. Binary Tree Maximum Path Sum Вам дан массив цен, где prices[i] — это цена данной акции в i-й день. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций. Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

👨‍💻 Алгоритм: 1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение. Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²). 2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй, одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство. В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием. 3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i]. Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]). Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5. И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]). Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6. Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1], то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом: max_profits[i] = left_profits[i] + right_profits[i+1] 😎 Решение:

class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        left_min = prices[0]
        right_max = prices[-1]

        length = len(prices)
        left_profits = [0] * length
        # pad the right DP array with an additional zero for convenience.
        right_profits = [0] * (length + 1)

        # construct the bidirectional DP array
        for l in range(1, length):
            left_profits[l] = max(left_profits[l - 1], prices[l] - left_min)
            left_min = min(left_min, prices[l])

            r = length - 1 - l
            right_profits[r] = max(right_profits[r + 1], right_max - prices[r])
            right_max = max(right_max, prices[r])

        max_profit = 0
        for i in range(0, length):
            max_profit = max(max_profit, left_profits[i] + right_profits[i + 1])

        return max_profit

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#medium Задача: 122. Best Time to Buy and Sell Stock II Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день. Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день. Найдите и верните максимальную прибыль, которую вы можете получить. Пример:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

👨‍💻 Алгоритм: 1️⃣Предположим, что дан массив: \[ 7, 1, 5, 3, 6, 4 \] Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение* 2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики. Математически говоря: Общая прибыль = ∑ (высота(пик i) - высота(впадина i)) 3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли. Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B. 😎 Решение:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        valley = prices[0]
        peak = prices[0]
        maxprofit = 0
        while i < len(prices) - 1:
            while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
                i += 1
            valley = prices[i]
            while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
                i += 1
            peak = prices[i]
            maxprofit += peak - valley
        return maxprofit

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Гранты покрывают от 25 до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

🔥 Битый код - канал для настоящих кодеров! 🔴 Тебе надоело сталкиваться с багами и ошибками в коде? 🔴 Хочешь прокачать свои навыки и узнать, как эффективно решать сложные задачи? ⭐️ Тогда тебе к нам! На канале Битый код ты найдешь: 🟡 Советы по оптимизации кода 🟡 Практические примеры и решения 🧠 Развивай свои навыки программирования вместе с нами и становись настоящим профессионалом! 🔥 Присоединяйся к Битому коду и учись исправлять ошибки как настоящий мастер.

ТОП-4 Курса по Нейросетям ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅За 3 месяца научим разрабатывать и внедрять в бизнес решения на основе ИИ, которые будут сокращать расходы и ускорять процессы в несколько раз! 💻Освоите Midjourney, Fooocus и другие полезные ИИ-инструменты. 📱Научитесь самостоятельно подбирать и тестировать ИИ под ваши цели. Выбрать #реклама 16+ tutortop.ru О рекламодателе

🤯 Чтобы не сидеть в творческом беспорядке, структурируй его с помощью Куб прогресса. Тут ты найдешь кучу советов для ITшника: 🟡 пользуйся полезными сайтами 🟡 подчеркивай интересные мысли 🛞 Начинай внедрять лайфхаки - создай структуру внутри себя

В приватной базе собесов уже больше 100 записей. Яндекс, Тиньков, Сбербанк, Самокат, Озон и другие крупные компании в базе.

#medium Задача: 117. Populating Next Right Pointers in Each Node II Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL. Изначально все указатели next установлены в NULL. Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

👨‍💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве. 3️⃣Подход, который мы будем использовать, предполагает структуру вложенных циклов, чтобы обойти необходимость NULL указателя. По сути, на каждом шаге мы фиксируем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и больше ничего. К тому времени, как мы закончим обработку заданного количества элементов, в очереди окажутся все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while. 😎 Решение:

class Solution:
    def connect(self, root: Optional["Node"]) -> Optional["Node"]:
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)

            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Как запустить собственный пет-проект и зарабатывать на нём зарплату senior-разработчика? На этом канале мы решаем сложные задачи, которые часто попадаются на собеседованиях. Но что, если перевернуть игру и вместо работы на кого-то запустить собственный пет-проект, который будет приносить деньги? Александр Рогачев запустил телеграм-канал Indie Hackers, где рассказывает про пет-проекты, которые приносят стабильный доход своим создателям. Без венчурных инвестиций, без бизнес-планов и команды. Разве такое возможно? Да! Несколько примеров: Агрегатор вакансий c доходом в 4000$ / месяц Плагин для Chrome с доходом 20000₽ / месяц Если вы в поиске свежих идей, которые могут обеспечить стабильный пассивных доход, подписывайтесь на канал Indie Hackers. Уверен, что там вы найдёте то самое, что зажгёт огонь в вашем сердце.

ТОП-4 Курса по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 116. Populating Next Right Pointers in Each Node Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL. Изначально все указатели next установлены в NULL. Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

👨‍💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве. 3️⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while. 😎 Решение:

import collections

class Solution:
    def connect(self, root: "Node") -> "Node":
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)
            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👩‍💻 Программирование теперь в телеграм! Вот обширная база материалов, которая ежедневно обновляется, выбирай своё направление: Обучение JavaScript с нуля Обучение Python с нуля Обучение Java с нуля Обучение HTML/CSS с нуля Обучение C/С++ с нуля Обучение С# с нуля Обучение SQL/GO/PHP с нуля Обучение Kotlin/Swift с нуля ⛓ Архив на 3489ГБ: Курсы, книги, шпаргалки, статьи, видео, ресурсы — всё собрано в одном месте: @roadmap_ready

Чем полезно ИТ-обучение, кроме программмирования? Только люди, прожившие 5 лет в глухом лесу, не слышали о том, что детей полезно учить цифровым навыкам еще с начальной школы. Но в чём же она, эта несомненная, по мнению педагогов, польза? Так ли уж необходимы все эти курсы? Да и в чем практический смысл таких знаний для повседневной жизни? 😊Вот это не ясно! Давайте разберёмся! 8 августа в 19:00 по МСК на бесплатной встрече педагоги из ИТ-школы Университета Иннополис готовы рассказать 💻где дети могут применять ИТ-навыки ежедневно, 🏃‍♂️какое преимущество появляется в будущем у детей, умеющих программировать, 📚зачем IT гуманитариям, 🎓как попробовать бесплатное обучение, чтоб понять, что ребенку это интересно и что занятия не будут заброшены через неделю. Регистрируйтесь, тобы помочь своим детям стать успешными Зарегистрироваться #реклама progmatica.innopolis.university О рекламодателе

#hard Задача: 115. Distinct Subsequences "Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t. Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком." Пример:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

👨‍💻 Алгоритм: 1️⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.** 2️⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.** 3️⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа. 😎 Решение:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:

        memo = {}

        def uniqueSubsequences(i: int, j: int) -> int:

            M, N = len(s), len(t)

            if i == M or j == N or M - i < N - j:
                return int(j == len(t))

            if (i, j) in memo:
                return memo[i, j]

            ans = uniqueSubsequences(i + 1, j)

            if s[i] == t[j]:
                ans += uniqueSubsequences(i + 1, j + 1)

            memo[i, j] = ans
            return ans

        return uniqueSubsequences(0, 0)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых