Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

def countSubstrings(s):
    def expandAroundCenter(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total_count = 0
    for i in range(len(s)):
        total_count += expandAroundCenter(i, i)  # For odd length palindromes
        total_count += expandAroundCenter(i, i + 1)  # For even length palindromes
    return total_count

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

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Вам дана строка s и массив строк-слов. Все строки-слова имеют одинаковую длину.

Объединенная строка - это строка, которая точно содержит все строки из любой перестановки слов, которые были объединены.

Например, если words = ["ab", "cd","ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются связанными строками. "acdbef" не является объединенной строкой, потому что это не объединение какой-либо перестановки слов.

Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.

Пример:

  
Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]  

👨‍💻 Алгоритм:

1️⃣Создаем словарь с подсчетом количества слов в words.

2️⃣Проходим по строке s, проверяя подстроки длины, равной len(words) * len(words[0]).

3️⃣Проверяем, содержит ли подстрока все слова из words в нужном количестве.

😎 Решение:

from collections import defaultdict  

class Solution:  
    def findSubstring(self, s: str, words: List[str]) -> List[int]:  
        if not s or not words:  
            return []  

        word_count = defaultdict(int)  
        for word in words:  
            word_count[word] += 1  

        substr_len = len(words) * len(words[0])  
        word_len = len(words[0])  
        result = []  

        for i in range(len(s) - substr_len + 1):  
            seen = defaultdict(int)  
            for j in range(i, i + substr_len, word_len):  
                word = s[j:j+word_len]  
                if word in word_count:  
                    seen[word] += 1  
                    if seen[word] > word_count[word]:  
                        break  
                else:  
                    break  
            else:  
                result.append(i)  

        return result

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

Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

👨‍💻 Алгоритм:

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

class Solution:
    def pruneTree(self, root):
        def containsOne(node):
            if not node:
                return False
            
            leftContainsOne = containsOne(node.left)
            rightContainsOne = containsOne(node.right)
            
            if not leftContainsOne:
                node.left = None
            if not rightContainsOne:
                node.right = None
            
            return node.val == 1 or leftContainsOne or rightContainsOne
        
        return root if containsOne(root) else None

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