Трудно понять алгоритм longestPalindrome

Question

Я нашел, что это решение имеет смысл для алгоритмического вопроса о нахождении самого длинного палиндрома в подстроке. Однако я изо всех сил пытаюсь понять, что на самом деле делает функция расширения. Я думал, что он будет работать из центра, но запись в консоли показывает, что он запускается для всей строки. Мне трудно понять, почему он вводит значение l oop для любого символа, который не совпадает с s[begin] === s[end], что, как я думал, препятствовало этой строке. Я не уверен, почему расширение также вызывается дважды. Кроме того, почему мы добавляем begin + 1 вместо begin при возврате подстроки. Код ниже. Любое разъяснение того, как работает расширение, будет оценено.

var longestPalindrome = function (s) {
    //either when empty string or is a single character
    if (!s || s.length <= 1) return s

    let longest = s.substring(0, 1)

    for (let i = 0; i < s.length; i++) {
        let temp = expand(s, i, i, 'first')
        // console.log(temp, 'i am the first')
        if (temp.length > longest.length) {
            longest = temp
        }
        temp = expand(s, i, i + 1, 'second')
        // console.log(temp, 'i am the second')
        if (temp.length > longest.length) {
            longest = temp
        }
    }
    return longest
}

const expand = (s, begin, end, counter) => {
    while (begin >= 0 && end <= s.length - 1 && s[begin] === s[end]) {
        console.log(s, 'i am string')
        console.log(begin, 'i am begin')
        console.log(end, 'i am begin')
        console.log(s[begin], s[end])
        console.log(counter)
        begin--
        end++
    }
    return s.substring(begin + 1, end)
}

console.log(longestPalindrome('cbbd'))
console.log(longestPalindrome('babad'))
console.log(longestPalindrome('ac'))
console.log(longestPalindrome('abb'))

Answer 1

Хорошо, скажем, мы хотим найти палиндром s, когда s = 'abba'.

примечание: Думайте о расширении как о палиндромном искателе, который берет центральный индекс. Имейте в виду, что позже я объясню, как работает расширение.

Мы сместим центр расширения с 0 до 3 (окончательный индекс). Во-первых, он проверяет расширение от begin = 0 и end = 0.

s = 'abba'

Если begin = 0 и end = 0, расширение возвращает «a».

v___
abba //only the palindrome from 0 is 'a'

Если begin = 0 и end = 1, расширение возвращает ''.

_v___
a bba //there are no palindrome from between 0 and 1 

Если begin = 1 и end = 1, расширение возвращает 'b'.

_v__
abba //only the palindrome from 1 is 'b'

Если начало = 1 и конец = 2, расширение возвращает «abba».

__v__
ab ba //the palindrome from between b and b is 'abba'

Если начало = 2 и конец = 2, расширение возвращает «b».

Если begin = 2 и end = 3, расширение возвращает ''.

Если begin = 3 и end = 3, расширение возвращает 'a'.

На этом этапе мы Протестировал все возможные палиндромы с. Наконец, код возвращает самый длинный палиндром на данный момент, который в данном случае будет «abba».

Обратите внимание, почему нам нужно выполнить расширение дважды. При i = 1 мы можем искать палиндром из центра.

_v__
abba

Но также с места между b и b

__v__
ab ba

Бывшие возвраты 'b' в то время как последний возвращает «abba». Вот почему вам нужно выполнить 2 расширения для каждого i.

---

Теперь, что именно происходит внутри функции расширения? Давайте использовать пример. s = 'aacdeedcba', а begin = 4 и end = 5.

Сначала l oop сначала проверяет, есть ли s [begin] == s [end].

____vv____
aacdeedcba

Очевидно, что 'e' === 'e' верно, поэтому мы начнем с левой стороны, а с правой стороны.

Снова мы проверим, s [начало] === s [конец].

___v__v____
aacdeedcba

Опять «d» === «d» верно, поэтому мы Сместим начало в левую сторону и конец в правую сторону.

мы проверим еще раз.

__v____v__
aacdeedcba

Снова, 'c' === 'c' - истина, поэтому мы сместимся и начнем с левой стороны, и конец к правой стороне.

мы проверим еще раз.

_v______v_
aacdeedcba

На этот раз 'a' === 'b' не соответствует действительности. Так что пока l oop остановлен. И функция расширения возвращает 'cdeed c'.

Answer 2

Однако я с трудом понимаю, что на самом деле делает функция расширения. Я думал, что он будет запускаться из центра, но запись в консоли показывает, что он запускается для всей строки

Палиндромы могут быть двух типов
1. Палиндромы одинаковой длины, например - "abba"
2. Палиндромы нечетной длины, например - "aba"

Теперь каждый индекс данной строки может быть центром любого из этих типов палиндромов. Таким образом, каждый индекс строки проверяется на эту возможность.

longestPalindrome функция принимает строку и для каждого индекса строки проверяет этот индекс как центр палиндрома нечетной длины и палиндрома четной длины.

expand функция берет два центральных индекса и начинает расширять их наружу. Для палиндрома нечетной длины центральный символ должен сравниваться с самим собой. Итак, expand вызывается с begin и end как один и тот же индекс.

Мне трудно понять, почему он вводит значение while l oop для любого символа, который не совпадает с s [begin] === s [end], как я и думал, что эта строка предотвращала ,

longestPalindrome отправит два индекса, так что это условие s[begin] === s[end] не соответствует действительности, но while l oop проверит и не расширит их. Вы можете запретить эту функцию с помощью функции longestPalindrome, если хотите.

Я не уверен, почему так же дважды вызывается расширение.

Это из-за два типа палиндромов на основе их длины. Вам необходимо проверить оба этих типа.

Кроме того, почему мы добавляем начало + 1, а не просто начало при возврате подстроки.

Это потому, что begin один раз, если выходит из while l oop. Вы можете сделать симуляцию на бумаге, чтобы лучше понять.