Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc"
Output: 3
👨💻 Алгоритм:
1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.
2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.
3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.
😎 Решение:
func countSubstrings(_ s: String) -> Int {
let sArray = Array(s)
var totalCount = 0
func expandAroundCenter(_ left: Int, _ right: Int) -> Int {
var left = left
var right = right
var count = 0
while left >= 0 && right < sArray.count && sArray[left] == sArray[right] {
count += 1
left -= 1
right += 1
}
return count
}
for i in 0..<sArray.count {
totalCount += expandAroundCenter(i, i)
totalCount += expandAroundCenter(i, i + 1)
}
return totalCount
}Ставь 👍 и забирай 📚 Базу знаний