Учитывая строку s, вернуть самую длинную

палиндром

подстрока

in s.

Пример 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Пример 2:

Input: s = "cbbd"
Output: "bb"

Ограничения:

  • 1 <= s.length <= 1000
  • s состоят только из цифр и английских букв.

Решения:

Одним из подходов к решению этой проблемы является использование подхода динамического программирования. Мы можем создать двумерный массив dp, где dp[i][j] — логическое значение, указывающее, является ли подстрока от s[i] до s[j] палиндромом. Затем мы можем заполнить этот массив, выполнив следующие шаги:

  1. Установите dp[i][i] на true для всех i (поскольку один символ всегда является палиндромом)
  2. Установите dp[i][i + 1] в true, если s[i] == s[i + 1] (поскольку строка длины 2 является палиндромом тогда и только тогда, когда два символа совпадают)
  3. Для k от 3 до n (где n — длина строки) установите dp[i][j] в true, если s[i] == s[j] и dp[i + 1][j - 1] равно true (поскольку строка длиной k является палиндромом, если два символа на концах совпадают, а подстрока между ними палиндром)

Как только мы заполнили массив dp, мы можем перебрать его и отследить самую длинную палиндромную подстроку.

Питон:

class Solution(object):
    def longestPalindrome(self, s):
        # Initialize the dp array with all False values
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        
        # Initialize variables to store the start and end indices of the longest palindromic substring
        start = 0
        end = 0
        
        # Fill in the dp array
        for k in range(1, n + 1):
            for i in range(n - k + 1):
                j = i + k - 1
                if k == 1:
                    dp[i][j] = True
                elif k == 2:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
                # Update the start and end indices if necessary
                if dp[i][j] and k > end - start + 1:
                    start = i
                    end = j
        
        # Return the longest palindromic substring
        return s[start:end + 1]

C#:

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
    bool[,] dp = new bool[n, n];
    string longest = "";

    // All substrings of length 1 are palindromes
    for (int i = 0; i < n; i++)
    {
        dp[i, i] = true;
        longest = s[i].ToString();
    }

    // Check substrings of length 2
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            dp[i, i + 1] = true;
            longest = s.Substring(i, 2);
        }
    }

    // Check substrings of length 3 and up
    for (int length = 3; length <= n; length++)
    {
        for (int i = 0; i < n - length + 1; i++)
        {
            int j = i + length - 1;
            if (s[i] == s[j] && dp[i + 1, j - 1])
            {
                dp[i, j] = true;
                longest = s.Substring(i, j - i + 1);
            }
        }
    }

    return longest;
    }
}

Java:

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String longest = "";

        // All substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            longest = s.substring(i, i + 1);
        }

        // Check substrings of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                longest = s.substring(i, i + 2);
            }
        }

        // Check substrings of length 3 and up
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    longest = s.substring(i, j + 1);
                }
            }
        }

        return longest;
    }
}

JavaScript:

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length;
    let dp = new Array(n);
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(n).fill(false);
    }
    let longest = "";

    // All substrings of length 1 are palindromes
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
        longest = s[i];
    }

    // Check substrings of length 2
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            longest = s.substring(i, i + 2);
        }
    }

    // Check substrings of length 3 and up
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i < n - length + 1; i++) {
            let j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                longest = s.substring(i, j + 1);
            }
        }
    }

    return longest;  
};

Типографический текст:

function longestPalindrome(s: string): string {
    let n = s.length;
    let dp: boolean[][] = new Array(n);
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(n).fill(false);
    }
    let longest = "";

    // All substrings of length 1 are palindromes
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
        longest = s[i];
    }

    // Check substrings of length 2
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            longest = s.substring(i, i + 2);
        }
    }

    // Check substrings of length 3 and up
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i < n - length + 1; i++) {
            let j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                longest = s.substring(i, j + 1);
            }
        }
    }

    return longest;
};

PHP:

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
         $n = strlen($s);
        $dp = array_fill(0, $n, array_fill(0, $n, false));
        $longest = "";

        // All substrings of length 1 are palindromes
        for ($i = 0; $i < $n; $i++) {
            $dp[$i][$i] = true;
            $longest = $s[$i];
        }

        // Check substrings of length 2
        for ($i = 0; $i < $n - 1; $i++) {
            if ($s[$i] === $s[$i + 1]) {
                $dp[$i][$i + 1] = true;
                $longest = substr($s, $i, 2);
            }
        }

        // Check substrings of length 3 and up
        for ($length = 3; $length <= $n; $length++) {
            for ($i = 0; $i < $n - $length + 1; $i++) {
                $j = $i + $length - 1;
                if ($s[$i] === $s[$j] && $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    $longest = substr($s, $i, $j - $i + 1);
                }
            }
        }

        return $longest;
    }
}

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