LeetCode Go — 5. Самая длинная палиндромная подстрока

Это 21-й день моего участия в Gengwen Challenge, смотрите подробности мероприятия:Обновить вызов

Для лучшего будущего придерживайтесь чистки зубовLeetCode!

тема

Для заданной строки s найти самую длинную подстроку палиндрома в s.

Пример 1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

Пример 2:

输入：s = "cbbd"
输出："bb"

Пример 3:

输入：s = "a"
输出："a"

Пример 4:

输入：s = "ac"
输出："a"

намекать:

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

Решение 1 — динамическое программирование

Идеи решения проблем

Палиндромная строка, которая противоположная вниз и прочитала все прочитать одну и ту же строку, поэтому мы можем думать, что строка палиндрома первого персонажа и последнего символа равна, то есть $s[i] == s[j]$ ,такой же, $s[i+1] == s[j-1]$ также должны быть удовлетворены.

код

func longestPalindrome(s string) string {
    l := len(s)
    if l < 2 {
        return s
    }

    r := make([][]bool, l)
    for i := 0; i < l; i++ {
        r[i] = make([]bool, l)
    }

    ml, si := 1, 0
    // 字串长度 sl = j - i + 1
    for sl := 2; sl <= l; sl++ {
        // 左边界 i
        for i := 0; i < l; i++ {
            // 右边界 j - i + 1 = sl
            j := i + sl -1
            if j >= l{
                break
            }
            if s[i] != s[j] {
                r[i][j] = false
            } else {
                if sl <= 3 {
                    r[i][j] = true
                } else {
                    r[i][j] = r[i+1][j-1]
                }
            }

            if r[i][j] && sl > ml {
                ml = sl
                si = i
            }
        }
    }
    return s[si:si+ml]
}

Результаты

执行用时：196 ms，在所有 Go 提交中击败了 17.20% 的用户
内存消耗：7.1 MB，在所有 Go 提交中击败了 20.45% 的用户

Анализ сложности

временная сложность: $O(n^2)$ ,в $n$ это длина строки.
Сложность пространства: $O(n^2)$ .

ссылка на тему

5. Самая длинная палиндромная подстрока