Учитывая строку 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]
палиндромом. Затем мы можем заполнить этот массив, выполнив следующие шаги:
- Установите
dp[i][i]
наtrue
для всехi
(поскольку один символ всегда является палиндромом) - Установите
dp[i][i + 1]
вtrue
, еслиs[i] == s[i + 1]
(поскольку строка длины 2 является палиндромом тогда и только тогда, когда два символа совпадают) - Для
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; } }
Надеюсь, это поможет! Дайте знать, если у вас появятся вопросы. Не забудьте подписаться и дать пару хлопков и комментариев