首页 > 代码库 > Leetcode-Longest Palindromic Substring
Leetcode-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.
Analysis:
We define the state d[i][j] as whether S[j-i+1...j] is palindromic, i.e., i is length, j the end of the substring.
d[i][j] is true, only when the char S[j-i+1]==S[j] and S[j-i+1...j-1] is palindromic, i.e., d[i-2][j-1] is true.
NOTE: the function substring() is time consuming.
Solution:
1 public class Solution { 2 public String longestPalindrome(String s) { 3 if (s.length()==0 || s.length()==1) return s; 4 String res = ""; 5 boolean[][] valid = new boolean[s.length()+1][s.length()]; 6 Arrays.fill(valid[0],true); 7 Arrays.fill(valid[1],true); 8 int start = 0, end = 0; 9 for (int i=2;i<=s.length();i++)10 for (int j=i-1;j<s.length();j++)11 if (valid[i-2][j-1] && s.charAt(j-i+1)==s.charAt(j)){12 valid[i][j]=true;13 //res = s.substring(j-i+1,j+1);14 start = j-i+1;15 end = j+1;16 } else valid[i][j]=false;17 18 return s.substring(start,end); 19 }20 }
Leetcode-Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。