Python | LeetCode

👩‍💻 Ищем Python разработчиков. Удалёнка, релокейт платим много! Специально для Вас, собираем лучшие вакансии для Python разработчиков с прямыми контактами в Telegram на канале @it_match_python Подпишись чтобы не упустить свой шанс получить лучший оффер! ➡️ Посмотреть вакансии

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! 5 занятий по теме «Промпт-инжиниринг». Регистрируйся для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 230. Kth Smallest Element in a BST Сложность: medium Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве. Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла. 2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение. 3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение. 😎 Решение:

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

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

Высшее образование дистанционно от 6700 ₽/мес. Поступи в Московский технологический институт в мае! — Высшее образование в московском вузе без выезда на сессии. — Полностью дистанционный онлайн-формат. — Обучайся дома, на работе, в путешествии. — Диплом государственного образца. — 73 направления и программы обучения. — Программа колледж + вуз без ЕГЭ. Скидка 10% на платное обучение при оплате за год. Подать заявку #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 1044. Longest Duplicate Substring Сложность: hard Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "". Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм: 1⃣Использование двоичного поиска для определения длины дублированной подстроки: Двоичный поиск используется для поиска максимальной длины дублированной подстроки. 2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины: Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок. 3⃣Хеширование с помощью функции rolling hash: Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов. 😎 Решение:

def longestDupSubstring(s):
    n = len(s)
    mod = 2**63 - 1

    def search(length):
        p = 26
        current_hash = 0
        p_length = pow(p, length, mod)
        hashes = set()

        for i in range(length):
            current_hash = (current_hash * p + ord(s[i])) % mod
        
        hashes.add(current_hash)
        
        for i in range(length, n):
            current_hash = (current_hash * p + ord(s[i]) - ord(s[i - length]) * p_length) % mod
            if current_hash in hashes:
                return i - length + 1
            hashes.add(current_hash)
        
        return -1

    left, right = 1, n - 1
    result = ""
    
    while left <= right:
        mid = (left + right) // 2
        start = search(mid)
        if start != -1:
            result = s[start:start + mid]
            left = mid + 1
        else:
            right = mid - 1
    
    return result

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

Профессия «Бизнес-аналитик» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python, BPMN, UML, EPC, IDEF. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше #реклама 16+ eduson.academy О рекламодателе

Задача: 277. Find the Celebrity Сложность: medium Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них. Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле). Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть. Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1. Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

👨‍💻 Алгоритм: 1⃣Найти потенциального кандидата на знаменитость: Использовать один проход через всех людей, чтобы определить возможного кандидата. Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b. 2⃣Реализовать функцию isCelebrity(candidate): Проверить, знает ли кандидат кого-либо из людей (исключая самих себя). Проверить, знают ли все остальные кандидата (исключая самого кандидата). Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью. 3⃣Возвращение результата: Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку. В противном случае вернуть -1. 😎 Решение:

from functools import lru_cache

class Solution:
    
    @lru_cache(maxsize=None)
    def cachedKnows(self, a, b):
        return knows(a, b)
    
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if self.cachedKnows(celebrity_candidate, i):
                celebrity_candidate = i
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if self.cachedKnows(i, j) or not self.cachedKnows(j, i):
                return False
        return True

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 923. 3Sum With Multiplicity Сложность: medium Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм: 1⃣Отсортировать массив arr. 2⃣Инициализировать счетчик для количества кортежей. Пройти по массиву тремя указателями i, j, и k: Для каждого i, установить j на i + 1, и k на конец массива. Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target. 3⃣Вернуть результат по модулю 10^9 + 7. 😎 Решение:

def threeSumMulti(arr, target):
    arr.sort()
    MOD = 10**9 + 7
    count = 0
    
    for i in range(len(arr)):
        j, k = i + 1, len(arr) - 1
        while j < k:
            sum_ = arr[i] + arr[j] + arr[k]
            if sum_ == target:
                if arr[j] == arr[k]:
                    count += (k - j + 1) * (k - j) // 2
                    break
                else:
                    left, right = 1, 1
                    while j + 1 < k and arr[j] == arr[j + 1]:
                        left += 1
                        j += 1
                    while k - 1 > j and arr[k] == arr[k - 1]:
                        right += 1
                        k -= 1
                    count += left * right
                    j += 1
                    k -= 1
            elif sum_ < target:
                j += 1
            else:
                k -= 1
                
    return count % MOD

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

Есть новости! Инженеры из QA.GURU проведут отдельный вебинар для продвинутых автоматизаторов на Python. Тема встречи: «Как стать Senior QA и выйти за рамки автотестов» — ведёт основатель проекта Стас Васенков. ❗Будет много практики и лайфкодинг. Стас покажет, как опытному автоматизатору расти дальше, разбираться в архитектуре и уверенно проходить собеседования в сильные команды. ⏳ Уже в этот четверг в 20:00 по МСК. В программе: — Что отличает Senior от Middle в 2025 году; — Почему одного написания тестов уже недостаточно; — Какие технические скиллы ждут на собеседованиях в топ-компаниях. И практика: — Перепишем автотесты с reqres.in и поднимем свой микросервис на FastAPI; — Освоим Kafka, gRPC, GraphQL, REST, SOAP, Postgres — через живой код; — Разберемся, как выйти за пределы фреймворка и мыслить как инженер. Спикер — Станислав Васенков: 10+ лет в автоматизации, ex-Head of QA в Госуслугах, автор allure-notifications, организатор QA-конференций, основатель QA.GURU. 🔗 Ссылка на регистрацию — места ещё есть.

Задача: 767. Reorganize String Сложность: medium Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми. Верните любую возможную перестановку строки s или верните "", если это невозможно. Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет. 2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации. 3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans. 😎 Решение:

import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        charCounts = [0] * 26
        for c in s:
            charCounts[ord(c) - ord('a')] += 1
        
        pq = []
        for i in range(26):
            if charCounts[i] > 0:
                heapq.heappush(pq, (-charCounts[i], chr(i + ord('a'))))
        
        result = []
        while pq:
            first = heapq.heappop(pq)
            if not result or first[1] != result[-1]:
                result.append(first[1])
                if -first[0] > 1:
                    heapq.heappush(pq, (first[0] + 1, first[1]))
            else:
                if not pq:
                    return ""
                second = heapq.heappop(pq)
                result.append(second[1])
                if -second[0] > 1:
                    heapq.heappush(pq, (second[0] + 1, second[1]))
                heapq.heappush(pq, first)
        
        return "".join(result)

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 957. Prison Cells After N Days Сложность: medium Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста. Каждый день статус камеры, занята она или пуста, меняется по следующим правилам: Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой. В противном случае, она становится пустой. Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей. Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n. Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше). Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

class Solution:
    def cellsToBitmap(self, cells):
        stateBitmap = 0
        for cell in cells:
            stateBitmap = (stateBitmap << 1) | cell
        return stateBitmap

    def nextDay(self, cells):
        newCells = [0] * len(cells)
        for i in range(1, len(cells) - 1):
            newCells[i] = 1 if cells[i - 1] == cells[i + 1] else 0
        return newCells

    def prisonAfterNDays(self, cells, N):
        seen = {}
        isFastForwarded = False

        while N > 0:
            if not isFastForwarded:
                stateBitmap = self.cellsToBitmap(cells)
                if stateBitmap in seen:
                    N %= seen[stateBitmap] - N
                    isFastForwarded = True
                else:
                    seen[stateBitmap] = N

            if N > 0:
                N -= 1
                cells = self.nextDay(cells)
        
        return cells

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

Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰 Почему это работает?✨ - Минимальные вложения. - Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций. - Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями. P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊 Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре. Подать заявку #реклама 16+ kata.academy О рекламодателе

Задача: 249. Group Shifted Strings Сложность: medium Выполните следующие операции сдвига на строке: Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza". Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz". Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов. Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ... Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке. Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

👨‍💻 Алгоритм: 1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26. 2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению. 3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups. 😎 Решение:

class Solution:
    def shiftLetter(self, letter, shift):
        return chr((ord(letter) - shift + 26) % 26 + ord('a'))
    
    def getHash(self, s):
        shift = ord(s[0])
        hashKey = ''.join(self.shiftLetter(letter, shift) for letter in s)
        return hashKey
    
    def groupStrings(self, strings):
        mapHashToList = defaultdict(list)
        
        for str in strings:
            hashKey = self.getHash(str)
            mapHashToList[hashKey].append(str)
        
        return list(mapHashToList.values())

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

Получи грант до 1,2 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1358. Number of Substrings Containing All Three Characters Сложность: medium Дана строка s, состоящая только из символов a, b и c. Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c. Пример:

Input: s = "abc"
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализация указателей и счетчиков: Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c. 2⃣Расширение окна: Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i. 3⃣Уменьшение окна и подсчет подстрок: Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится. Верните итоговое количество подстрок. 😎 Решение:

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = 0
        char_count = {'a': 0, 'b': 0, 'c': 0}
        i = 0
        
        for j in range(len(s)):
            char_count[s[j]] += 1
            
            while all(char_count[char] > 0 for char in "abc"):
                count += len(s) - j
                char_count[s[i]] -= 1
                i += 1
        
        return count

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

Задача: 633. Sum of Square Numbers Сложность: medium Учитывая целое неотрицательное число c, решите, существуют ли два целых числа a и b такие, что a2 + b2 = c. Пример:

Input: c = 5
Output: true

👨‍💻 Алгоритм: 1⃣Проверка границ: Проверьте, если c меньше 0, немедленно верните false, так как сумма квадратов двух целых чисел не может быть отрицательной. 2⃣Инициализация указателей: Используйте два указателя a и b. Инициализируйте a на 0 и b на значение квадратного корня из c. Поиск решения: Используйте цикл для поиска a и b, таких что a^2 + b^2 == c: Если a^2 + b^2 равно c, верните true. Если a^2 + b^2 меньше c, увеличьте a на 1. Если a^2 + b^2 больше c, уменьшите b на 1. 3⃣Возвращение результата: Если цикл завершится без нахождения подходящих a и b, верните false. 😎 Решение:

import math

def judgeSquareSum(c: int) -> bool:
    a = 0
    b = int(math.sqrt(c))
    while a <= b:
        total = a * a + b * b
        if total == c:
            return true
        elif total < c:
            a += 1
        else:
            b -= 1
    return false'

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

Почему выбирают PostgreSQL как сервис от РТК-ЦОД? Сервис PostgreSQL от РТК-ЦОД позволяет быстро развернуть, эксплуатировать и масштабировать базу данных в облаке. Процесс установки и настройки полностью автоматизирован. Почему выбирают нас? — Личный кабинет — Надежное хранение данных: дата-центры уровня Tier III в России, сертифицированные Uptime Institute — Детальный SLA — Оптимальная конфигурация: выделенный кластер только под вас — Опция администрирования вашей базы данных — Квалифицированная техподдержка в режиме 24х7 ✅ 30 дней бесплатно: тестируйте наш сервис с полным доступом ко всем возможностям. Оставьте заявку на www.cloud.rt.ru Узнать больше #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 820. Short Encoding of Words Сложность: medium Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что: words.length == indices.length Опорная строка s заканчивается символом '#'. Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i]. Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов. Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

👨‍💻 Алгоритм: 1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством. 2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'. 3⃣В конце вернем длину полученной опорной строки. 😎 Решение:

class Solution:
    def minimumLengthEncoding(self, words):
        good = set(words)
        for word in words:
            for k in range(1, len(word)):
                good.discard(wo

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