Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний