首页 > 代码库 > LeetCode：Longest Palindromic Substring
LeetCode：Longest Palindromic Substring
Longest Palindromic Substring
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.
动态规划解法
T(n) = O(n^2) ,S(n) = O(n^2);
Solution：
public class Solution { private static int MAX_LENGH = 1000; public String longestPalindrome(String s) { char[] ch = s.toCharArray(); int len = s.length(); int maxLen = 1; int longestBegin = 0; boolean[][] table = new boolean[len+1][len+1]; // Arrays.fill(table,false); for(int i = 0; i < len; i++){ table[i][i] = true; } for(int i = 0; i < len-1; i++){ if(ch[i] == ch[i+1]){ table[i][i+1] = true; longestBegin = i; maxLen = 2; } } for(int l = 3 ; l <= len; l++){ for(int i = 0; i< len - l+1; i++){ int j = i + l -1; if(ch[i] == ch[j] && table[i+1][j-1]){ table[i][j] = true; maxLen = l; longestBegin = i; } } } return s.substring(longestBegin,longestBegin + maxLen); }}
O(n) 线性时间复杂度算法
极其酷炫掉渣天的方法
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。