описание проблемы

Для данной строки ваша задача - посчитать, сколько палиндромных подстрок в этой строке.

Подстроки с разными начальными индексами или конечными индексами считаются разными подстроками, даже если они состоят из одинаковых символов.

Пример 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".

Примечание.

  1. Длина входной строки не должна превышать 1000.

Решение:

Время выполнения: 76 мс

Использование памяти: 37,1 МБ.

В этом решении мы использовали две пары из двух указателей для обхода строки.

Давайте рассмотрим два примера, чтобы увидеть, как это работает:

Примечание: ниже «l» обозначает левый указатель, «r» обозначает правый указатель.

Используя эти четыре указателя, так что i в качестве лидера будет проходить каждую букву, поскольку каждая буква является палиндромной подстрокой, j будет отвечать за следующую букву i, чтобы проверить палиндромные подстроки, длина которых равна 2, левый и правый указатели будут проходить через соседи, поэтому они будут отвечать за палиндромные подстроки, длина которых больше 2.

Надеюсь, этот блог будет вам полезен. Спасибо за чтение.