刷题LeetCode：5.最长回文子串

大家好，欢迎来到IT知识分享网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s ，找出 s 中的最长回文子串。

题目分析

动态规划

用 P(i,j) 表示字符串第 i 到 j 个字母组成的串是否为回文串：

• P(i,j) = true，字符串第 i 到 j 个字母组成的子串是回文
• P(i,j) = false，其他情况

存在动态规划方程： P(i,j) = P(i + 1,j + 1) && s(i) == s(j)

• s(i) == s(j) : s 的第 i 和 j 个字母相同
• 若 i == j ，P(i,j) = true

代码实现

public class LongestPalindrome_5 { public static void main(String[] args) { LongestPalindrome_5 main = new LongestPalindrome_5(); String result = main.longestPalindrome("dddddababad"); System.out.println("result:" + result); } public String longestPalindrome(String s) { int len = s.length(); if (len == 1) { return s; } int begin = 0; int maxLen = 1; boolean[][] result = new boolean[len][len]; char[] charArray = s.toCharArray(); // 初始化 for (int i = 0; i < len; i++) { result[i][i] = true; } for (int sbLen = 2; sbLen <= len; sbLen++) { for (int i = 0; i < len; i++) { int end = i + sbLen - 1; // 小心数组越界 if (end >= len) { break; } if (charArray[i] == charArray[end]) { // 长度为 2 且字符相同 if (sbLen == 2) { result[i][end] = true; } else { result[i][end] = result[i + 1][end - 1]; } } else { result[i][end] = false; } // 取最大长度 if (result[i][end] && maxLen < sbLen) { maxLen = sbLen; begin = i; } } } return s.substring(begin, begin + maxLen); } }

运行结果：

复杂度

• 时间复杂度：O(n^2)，其中 n 是字符串长度。
• 空间复杂度：O(n^2)，存储动态规划状态需要的空间。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！