Есть много видеороликов, в которых говорится об этом вопросе о самой длинной подстроке палиндрома, но есть еще некоторые детали, на которые мне потребовалось некоторое время, чтобы понять это. Я немного разбил его, чтобы мы могли лучше понять подход. Я также включил некоторые пояснения по расчетам.
Вопрос:
Как найти палиндромную подстроку (расширить вокруг центра)
Начиная с центра подстроки, чтобы оценить, является ли подстрока палиндромом. Если буква слева от центра s[center-1]
равна букве справа от центра s[center+1]
, мы продолжаем двигаться к следующей букве с каждой стороны, пока не наткнемся на неравенство:
s[center - 1] === s[center + 1] s[center - 2] === s[center + 2] ... === ... s[center - n] === s[center + n] s[center - n -1] !== s[center + n + 1]//exit
Затем мы находимs.substring(center — n, center + n + 1)
— палиндромную подстроку (конечный индекс javascript substring() не включает, поэтому нам нужно добавить его, чтобы захватить всю подстроку).
Существует два сценария использования центра(ов) в строке:
- в палиндроме есть только один центр
s[i]
, когда его длина нечетна: центр «babad» — это «b» с индексом 2 - есть два центра
s[i]
иs[i+1]
в палиндроме, когда его длина четна: центрами «cbbd» являются «b» с индексом 1 и «b» с индексом 2
Мы не знаем, какие строки мы получаем, поэтому нам нужно включить оба сценария.
Код и объяснение
Я установил функцию с именем findLPS(s, center1, center2)
, которая принимает строку, которую мы оцениваем, и оба центра. В функции есть две переменные left
и right
для отслеживания начального и конечного индексов подстроки. Пока left
и right
находятся в границах, а s[left]===s[right]
продолжаем движение left
влево и right
вправо. Когда условие не было выполнено, мы выходим из цикла while и возвращаем длину подстроки right-left-1
.
Почему длина подстроки right-left-1
, а не right-left+1
?
For example, when s is “aba”,left
andright
start at index 1, thenleft--, left = 1, 0, -1
right++, right = 1, 2, 3
When we break out of the while loop,left
is -1 andright
is 3. We need to move back an index on both sides:substring.length = (right-1)-(left+1)+1= (3–1)-(-1+1)+1 = 3
which equals toright-left-1 = 3-(-1)-1 = 3
В функции longestPalindrome я использовал цикл for для оценки каждой буквы в строке, чтобы увидеть, является ли она центром палиндрома, как упоминалось ранее, нам нужно включить оба сценария центра (центров). Если len
длиннее longest
, мы можем присвоить len
longest
и начать вычислять индексы start
и end
самой длинной палиндромной подстроки, которую мы хотим вернуть.
Почему начало i - Math.floor((len -1)/2)
, а не i — Math.floor(len/2)
?
For example, i is at the center of the palindrome and we want to calculate the start index of the string: "aba", i = 1, len = 3 i - Math.floor(len/2) = 1 - 1 = 0 i - Math.floor((len-1)/2) = 1 - 1 = 0 "cbbc", i =1, len = 4 i - Math.floor(len/2) = 1-2 = -1 //index out of bounds i - Math.floor((len-1)/2) = 1 - 1 = 0 //index in the bounds We are dealing with indexes here, when the length of the returned substring is even and the centers are i and i+1. We are using i to calculate the start and end indexes. Use "cbbc" again: c b b c 0 1 2 3 i = 1 len = 4 len/2 = 2 Math.floor((len-1)/2) = 1 We can see that i is "closer" to the start index than to the end index. So for end index we do not need to minus one off the len: end = 1 + Math.floor(4/2) = 3 start = i - Math.floor((len-1)/2) = 0
Анализ сложности
Временная сложность: O(n²). Поскольку расширение палиндрома вокруг его центра может занять O (n) времени, общая сложность составляет O (n²).
Пространственная сложность: O(1).
Ресурс: