ar
Feedback
Python | LeetCode

Python | LeetCode

الذهاب إلى القناة على Telegram
9 170
المشتركون
-724 ساعات
-187 أيام
-7030 أيام
أرشيف المشاركات
Задача: 1247. Minimum Swaps to Make Strings Equal Сложность: hard Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:
Input: arr = [1,2]
Output: 2
👨‍💻 Алгоритм: 1⃣Подсчет несоответствующих пар: Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'. 2⃣Проверка четности: Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1. 3⃣Вычисление минимального количества замен: Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2. Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2. 😎 Решение:
def minimumSwap(s1, s2):
    xy = yx = 0
    for a, b in zip(s1, s2):
        if a == 'x' and b == 'y':
            xy += 1
        elif a == 'y' and b == 'x':
            yx += 1
    if (xy + yx) % 2 != 0:
        return -1
    return xy // 2 + yx // 2 + (xy % 2) * 2
Ставь 👍 и забирай 📚 Базу знаний

Задача: 784. Letter Case Permutation Сложность: medium Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример:
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
👨‍💻 Алгоритм: 1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине. 2⃣Если c является цифрой, мы добавим его к каждому слову. 3⃣Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации. 😎 Решение:
class Solution:
    def letterCasePermutation(self, S):
        ans = [[]]

        for char in S:
            n = len(ans)
            if char.isalpha():
                for i in range(n):
                    ans.append(ans[i][:])
                    ans[i].append(char.lower())
                    ans[n+i].append(char.upper())
            else:
                for i in range(n):
                    ans[i].append(char)

        return list(map("".join, ans))
Ставь 👍 и забирай 📚 Базу знаний

Задача: 987. Vertical Order Traversal of a Binary Tree Сложность: medium Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным. Верните пересечение этих двух списков интервалов. Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b. Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3]. Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨‍💻 Алгоритм: 1⃣Инициализация указателей: Создать словарь для хранения узлов по их координатам (col, row). Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)). 2⃣Поиск пересечений: Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row). Добавить левый потомок в очередь с координатами (row + 1, col - 1). Добавить правый потомок в очередь с координатами (row + 1, col + 1). 3⃣Возврат результата: Отсортировать ключи словаря по col и затем по row. Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список. 😎 Решение:
from collections import defaultdict, deque

class Solution:
    def verticalTraversal(self, root):
        col_table = defaultdict(list)
        queue = deque([(root, 0, 0)])
        
        while queue:
            node, row, col = queue.popleft()
            if node:
                col_table[col].append((row, node.val))
                queue.append((node.left, row + 1, col - 1))
                queue.append((node.right, row + 1, col + 1))
        
        result = []
        for col in sorted(col_table.keys()):
            col_table[col].sort()
            result.append([val for row, val in col_table[col]])
        
        return result
Ставь 👍 и забирай 📚 Базу знаний

Научу китайскому языку, даже если у вас нет дисциплины! Я родилась в Китае и этот язык мне родной. И я больше не могу молчать
Научу китайскому языку, даже если у вас нет дисциплины! Я родилась в Китае и этот язык мне родной. И я больше не могу молчать: 90% преподавателей китайского учат через зубрёжку иероглифов, тонов и фраз. Никакой нормальный человек этого не выдержит! Я предлагаю совсем другую систему: без зубрёжки, всего 30-60 минут в день. ✅ Через ассоциации и ключи вы легко запомните 750 иероглифов. ✅ Перестанете путать тоны за 1-2 занятия. ✅ Начнете говорить без акцента и понимать китайцев с полуслова. Приглашаю на бесплатный вебинар, где расскажу про свой способ подробнее. Запишитесь сейчас и получите в подарок полезную шпаргалку по тонам Если ссылка не работает, места закончились. Записаться #реклама 16+ club-nihaostudy.ru О рекламодателе

Задача: 1512. Number of Good Pairs Сложность: easy Дан массив целых чисел nums, верните количество хороших пар. Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j. Пример:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерируйте i от 0 до nums.length: Итерируйте j от i + 1 до nums.length: Если nums[i] == nums[j], увеличьте ans на 1. 3⃣Верните ans. 😎 Решение:
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    ans += 1
        return ans
Ставь 👍 и забирай 📚 Базу знаний

Задача: 1023. Camelcase Matching Сложность: medium Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа. Пример:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:
class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def matches(query, pattern):
            i, j = 0, 0
            while i < len(query):
                if j < len(pattern) and query[i] == pattern[j]:
                    j += 1
                elif query[i].isupper():
                    return False
                i += 1
            return j == len(pattern)
        
        return [matches(query, pattern) for query in queries]
Ставь 👍 и забирай 📚 Базу знаний

Задача: 928. Minimize Malware Spread II Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом. Пример:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
👨‍💻 Алгоритм: 1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов. 2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом. 😎 Решение:
def minMalwareSpread(graph, initial):
    n = len(graph)
    
    def dfs(node, visited):
        stack = [node]
        while stack:
            u = stack.pop()
            for v in range(n):
                if graph[u][v] == 1 and v not in visited:
                    visited.add(v)
                    stack.append(v)
    
    components = []
    visited = set()
    for i in range(n):
        if i not in visited:
            component = set()
            dfs(i, component)
            components.append(component)
            visited.update(component)
    
    infected_in_component = [0] * len(components)
    node_to_component = {}
    for idx, component in enumerate(components):
        for node in component:
            node_to_component[node] = idx
            if node in initial:
                infected_in_component[idx] += 1
    
    min_infected = float('inf')
    result_node = min(initial)
    for node in initial:
        component_idx = node_to_component[node]
        if infected_in_component[component_idx] == 1:
            component_size = len(components[component_idx])
            if component_size < min_infected or (component_size == min_infected and node < result_node):
                min_infected = component_size
                result_node = node
    
    return result_node
Ставь 👍 и забирай 📚 Базу знаний

Задача: 720. Longest Word in Dictionary Сложность: medium Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова. Пример:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
👨‍💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:
def longestWord(words):
    words.sort()
    valid_words = {""}
    longest = ""
    for word in words:
        if word[:-1] in valid_words:
            valid_words.add(word)
            if len(word) > len(longest):
                longest = word
    return longest
Ставь 👍 и забирай 📚 Базу знаний

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен т
Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 868. Binary Gap Сложность: easy Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0. Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3. Пример:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.
👨‍💻 Алгоритм: 1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1. 2⃣Используйте список A, чтобы найти максимальное расстояние между соседними значениями. Для этого пройдите по списку и вычислите разницу между каждым соседним элементом. 3⃣Верните найденное максимальное расстояние. 😎 Решение:
class Solution:
    def binaryGap(self, N: int) -> int:
        A = [i for i in range(32) if (N >> i) & 1]
        return max((A[i + 1] - A[i] for i in range(len(A) - 1)), default=0)
Ставь 👍 и забирай 📚 Базу знаний

Задача: 942. DI String Match Сложность: easy Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них. Пример:
Input: s = "IDID"
Output: [0,4,1,3,2]
👨‍💻 Алгоритм: 1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке. 2⃣Создать массив perm длиной n + 1. Пройти по строке s: Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low. Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high. Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm. 3⃣Вернуть массив perm. 😎 Решение:
def diStringMatch(s):
    n = len(s)
    low, high = 0, n
    perm = [0] * (n + 1)
    
    for i in range(n):
        if s[i] == 'I':
            perm[i] = low
            low += 1
        else:
            perm[i] = high
            high -= 1
    
    perm[n] = low
    return perm
Ставь 👍 и забирай 📚 Базу знаний

Задача: 311. Sparse Matrix Multiplication Сложность: medium Даны две разреженные матрицы mat1 размером m x k и mat2 размером
Задача: 311. Sparse Matrix Multiplication Сложность: medium Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно. Пример:
Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]
👨‍💻 Алгоритм: 1⃣Инициализация результирующей матрицы Создайте результирующую матрицу result размером m x n, заполненную нулями. 2⃣Хранение ненулевых элементов Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map. 3⃣Вычисление произведения Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j]. 😎 Решение:
class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        n = len(mat1)
        k = len(mat1[0])
        m = len(mat2[0])
        
        ans = [[0] * m for _ in range(n)]
        
        for rowIndex in range(n):
            for elementIndex in range(k):
                if mat1[rowIndex][elementIndex] != 0:
                    for colIndex in range(m):
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
        
        return ans
Ставь 👍 и забирай 📚 Базу знаний

Задача: 409. Longest Palindrome Сложность: easy Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом. Пример:
Input: s = "abccccdd"
Output: 7
👨‍💻 Алгоритм: 1⃣Создайте словарь для подсчета количества каждого символа в строке. 2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома. 3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа. 😎 Решение:
def longestPalindrome(s):
    charCount = {}
    for char in s:
        charCount[char] = charCount.get(char, 0) + 1
    length = 0
    oddFound = False
    for count in charCount.values:
        if count % 2 == 0:
            length += count
        else:
            length += count - 1
            oddFound = True
    return length + 1 if oddFound else length
Ставь 👍 и забирай 📚 Базу знаний

👩‍💻 Стажировки и вакансии для Python разработчиков. - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR
👩‍💻 Стажировки и вакансии для Python разработчиков. - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR в Telegram 👉 @jobs_python Больше тут: 🤖 ML & DS 👩‍💻 DevOps 👨‍✈️ ИБ & OSINT 👣 Go 👩‍💻 Mobile 👩‍💻 C# 👩‍💻 Node.js 👩‍💻 Python 🔎 QA 👩‍💻 Java 👩‍💻 UX/UI 👩‍💻 Frontend 🖼️ PHP 📋 Analyst 💼 1C 🖥 SQL 👩‍💻 IT HR Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Все алгоритмы нейрографики от инструктора. 👍Игровой бесплатный мини-курс. ✨4 дня практики для специалистов нейрографики, которые боятся начать работать с клиентами. Всего за 4 урока вы научитесь избавляться от негативных эмоций, наполняться энергией вдохновения для исполнения заветных желаний и создания жизни своей мечты! Меня зовут Наталья Шевякова (психолог, эмотолог). 🎓Я инструктор НейроГрафики и с радостью приглашаю вас на обучающий игровой мини-курс. Его прошли уже более 15000 человек. Всё покажу на живых примерах, просто, с элементами игры — и вы сами почувствуете, как это работает! Это получается у всех! Переходите по ссылке, проходите курс. Смотреть #реклама 16+ neuronataly.com О рекламодателе

Задача: 1216. Valid Palindrome III Сложность: hard Дана строка s и целое число k. Верните true, если s является k-палиндромом. Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов. Пример:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.
👨‍💻 Алгоритм: 1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j. 2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo. 3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление. 😎 Решение:
class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        memo = [[None] * n for _ in range(n)]

        def isValidPalindromeHelper(i, j):
            if i == j:
                return 0
            if i == j - 1:
                return 1 if s[i] != s[j] else 0
            if memo[i][j] is not None:
                return memo[i][j]
            if s[i] == s[j]:
                memo[i][j] = isValidPalindromeHelper(i + 1, j - 1)
            else:
                memo[i][j] = 1 + min(isValidPalindromeHelper(i + 1, j), isValidPalindromeHelper(i, j - 1))
            return memo[i][j]

        return isValidPalindromeHelper(0, n - 1) <= k
Ставь 👍 и забирай 📚 Базу знаний

Задача: 1036. Escape a Large Maze Сложность: hard Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов. Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
👨‍💻 Алгоритм: 1⃣Обработка входных данных: Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked. 2⃣Проверка простого случая: Если список blocked пуст, верните true, так как путь не будет заблокирован. Проверка начальной или целевой клетки: Если исходная или целевая клетка заблокированы, верните false. 3⃣Поиск пути с использованием BFS или DFS: Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток. Если обнаружен путь, верните true, в противном случае верните false. 😎 Решение:
from collections import deque

def isEscapePossible(blocked, source, target):
    blocked = set(map(tuple, blocked))
    source = tuple(source)
    target = tuple(target)
    
    if source in blocked or target in blocked:
        return False

    def bfs(start, end):
        queue = deque([start])
        visited = set([start])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        max_area = len(blocked) * (len(blocked) - 1) // 2
        
        while queue:
            if len(visited) > max_area:
                return True
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in visited and (nx, ny) not in blocked:
                    if (nx, ny) == end:
                        return True
                    queue.append((nx, ny))
                    visited.add((nx, ny))
        return False
    
    return bfs(source, target) and bfs(target, source)
Ставь 👍 и забирай 📚 Базу знаний

Задача: 212. Word Search II Сложность: hard Дана m на n доска символов и список строк words, верните все слова, находящиеся н
Задача: 212. Word Search II Сложность: hard Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске. Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове. Пример:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
👨‍💻 Алгоритм: 1️⃣ Построение Trie: Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже. 2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки: Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell). 3️⃣ Обход соседних ячеек: В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell). На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале. 😎 Решение:
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        WORD_KEY = "$"

        trie = {}
        for word in words:
            node = trie
            for letter in word:
                node = node.setdefault(letter, {})
            node[WORD_KEY] = word

        rowNum = len(board)
        colNum = len(board[0])
        matchedWords = []

        def backtracking(row, col, parent):
            letter = board[row][col]
            currNode = parent[letter]

            word_match = currNode.pop(WORD_KEY, False)
            if word_match:
                matchedWords.append(word_match)

            board[row][col] = "#"

            for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                newRow, newCol = row + rowOffset, col + colOffset
                if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
                    continue
                if board[newRow][newCol] not in currNode:
                    continue
                backtracking(newRow, newCol, currNode)

            board[row][col] = letter

            if not currNode:
                parent.pop(letter)

        for row in range(rowNum):
            for col in range(colNum):
                if board[row][col] in trie:
                    backtracking(row, col, trie)

        return matchedWords
Ставь 👍 и забирай 📚 Базу знаний

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен т
Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе