首页 > 代码库 > [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.
很经典的DP问题：
算法分析：
思路1：最土的算法，将所有的子串求出来，再选出最长的回文子串。不用试，肯定超时。
思路2：挑出最短的回文串（单个字符，或者两个相邻的相同字符），然后向两端辐射，时间复杂度O(n^2)，空间复杂度可以优化到O(1)【我木有优化= =】
代码如下：
1 public String longestPalindrome(String s) { 2 if(s == null || s.length() == 0) return ""; 3 String maxsub = ""; 4 for(int i = 0; i < s.length(); i++){ 5 String str = getPalindrome(s, i, i,s.length()); 6 if(str.length() > maxsub.length()) 7 maxsub = str; 8 if(i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)){ 9 str = getPalindrome(s, i, i + 1,s.length());10 if(str.length() > maxsub.length())11 maxsub = str;12 }13 }14 return maxsub;15 }16 private String getPalindrome(String s,int begin,int end,int prime){17 while(begin >= 0 && end < s.length()){18 if(s.charAt(begin) == s.charAt(end)){19 begin--;20 end++;21 }else{22 break;23 }24 }25 return s.substring(begin+1, end);26 }
思路3：DP
参考同学的做法：
dp[i][j] 代表从i到j的子串是否是palindrome。自下而上自左而右计算dp数组。时空复杂度都是 O(n^2)。
dp[i][j]=1 if:
- i=j；
- s.charAt(i)==s.charAt(j) && j-i<2
- s.charAt(i)==s.charAt(j) && dp[i+1][j-1]==1
1 public class Solution { 2 public String longestPalindrome(String s) { 3 if(s == null || s.length() == 0) return ""; 4 boolean[][] dp = new boolean[s.length()][s.length()]; 5 int start = 0, end = 0,len = 0; 6 for(int i = s.length() - 1; i >= 0; i--){ 7 for(int j = i; j < s.length(); j++){ 8 if(i == j || (s.charAt(i) == s.charAt(j) && j - i == 1) || (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1])){ 9 dp[i][j] = true;10 if(j - i + 1 > len){11 len = j - i + 1;12 start = i;13 end = j;14 }15 }16 }17 }18 return s.substring(start, end + 1);19 }20 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。