首页 > 代码库 > Leetcode: Longest Palindromic Substring. java
Leetcode: Longest Palindromic Substring. java
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
动态规划
public class Solution { public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; int n = s.length(); int max = 0, start = 0, end = 0; boolean[][] c = new boolean[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i][j] = i >= j ? true : false; } } //c[i][j] 记录从第i个到第j个是不是回文。 for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { if (s.charAt(i) == s.charAt(j) && c[i+1][j-1]) { c[i][j] = true; if (j - i + 1 > max) { max = j - i + 1; start = i; end = j; } } else c[i][j] = false; } } return s.substring(start, end+1); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。