описание проблемы
Для данной строки ваша задача - посчитать, сколько палиндромных подстрок в этой строке.
Подстроки с разными начальными индексами или конечными индексами считаются разными подстроками, даже если они состоят из одинаковых символов.
Пример 1:
Input: "ABCBA" Output: 7 Explanation: Three palindromic strings: "A", "B", "C", "B", "A", "BCB", "ABCBA".
Пример 2:
Input: "AAA" Output: 6 Explanation: Six palindromic strings: "A", "A", "A", "AA", "AA", "AAA".
Примечание.
- Длина входной строки не должна превышать 1000.
Решение:
Время выполнения: 76 мс
Использование памяти: 37,1 МБ.
В этом решении мы использовали две пары из двух указателей для обхода строки.
Давайте рассмотрим два примера, чтобы увидеть, как это работает:
Примечание: ниже «l» обозначает левый указатель, «r» обозначает правый указатель.
Используя эти четыре указателя, так что i в качестве лидера будет проходить каждую букву, поскольку каждая буква является палиндромной подстрокой, j будет отвечать за следующую букву i, чтобы проверить палиндромные подстроки, длина которых равна 2, левый и правый указатели будут проходить через соседи, поэтому они будут отвечать за палиндромные подстроки, длина которых больше 2.
Надеюсь, этот блог будет вам полезен. Спасибо за чтение.