了解最长的回文算法很困难

Question

我发现此解决方案对于在子字符串中找到最长回文的算法问题有意义。但是，我正在努力了解扩展功能的实际作用。我以为它将从中心运行，但是控制台日志显示它针对整个字符串运行。我很难理解为什么它会为任何与s[begin] === s[end]不同的字符进入while循环，这是我认为这行所防止的。我不确定为什么expand被两次调用。另外，为什么在返回子字符串时为什么添加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 ='abba'时找到s的回文。

注意：可以将扩展视为接受中心索引的回文查找器。请记住，我稍后将解释扩展的工作方式

我们将展开的中心从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'。

如果开始= 2，结束= 3，则扩展返回''。

如果开始= 3，结束= 3，则扩展返回'a'。

至此，我们已经测试了所有可能的s回文。最后，代码返回到目前为止最长的回文，在这种情况下将为'abba'。

注意为什么我们需要执行两次扩展。在i = 1时，我们可以从中心查找回文。

_v__
abba

也是从b和b之间的地方

__v__
ab ba

前者返回“ b”，而后者返回“ abba”。这就是为什么您需要对每个i执行2次扩展的原因。

---

现在，扩展函数内部到底发生了什么？让我们使用示例。 s ='aacdeedcba'，开始= 4，结束= 5。

首先，while循环检查s [begin] == s [end]。

____vv____
aacdeedcba

显然'e'==='e'是正确的，所以我们将开始从左侧移到，然后从右侧移到。

同样，我们将检查s [begin] === s [end]。

___v__v____
aacdeedcba

同样，'d'==='d'是正确的，因此我们将开始从左侧移到结束，然后移到右侧。

我们将再次检查。

__v____v__
aacdeedcba

同样，'c'==='c'是正确的，因此我们将开始从左侧移到，然后从右侧移到。

我们将再次检查。

_v______v_
aacdeedcba

这次，'a'==='b'不正确。因此，while循环已停止。扩展功能返回“ cdeedc”。

Answer 2

但是，我正在努力了解扩展功能的实际作用。我以为它将从中心运行，但是控制台日志显示它针对整个字符串运行

回文可以是两种类型1.平均长度的回文，例如-“阿巴”2.奇长回文，例如-“ aba”

现在，给定字符串的每个索引可以位于这些回文类型中的任何一个的中心。因此，将测试字符串的每个索引是否存在这种可能性。

[longestPalindrome函数接收字符串，并且对于字符串的每个索引，它将字符串作为奇数回文和偶数回文的中心进行测试。

expand函数采用两个中心索引，并开始向外扩展它们。对于奇长回文，应该将中心字符与其自身进行比较。因此，以expand和begin作为相同的索引调用end。

我很难理解为什么它会为与s [begin] === s [end]不同的任何字符进入while循环，这就是我认为这行所要防止的。

longestPalindrome将发送两个索引，以使此条件s[begin] === s[end]不成立，但while循环将检查并且不会进一步扩展它们。如果需要，可以从longestPalindrome功能中阻止此功能。

我也不知道为什么expand被两次调用。

这是由于回文基于其长度的两种类型。您需要测试这两种类型。

另外，为什么返回子字符串时我们要添加begin + 1而不是仅仅开始。

这是因为如果从begin循环中出来，则while为1。您可以在纸上进行模拟以更好地理解。