*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.

• Example 1:
  Input: “babad”
  Output: “bab”
  Note: “aba” is also a valid answer.
• Example 2:
  Input: “cbbd”
  Output: “bb”
  中等难度就开始搞不定了，也是很心累了。参考

解法一

遍历s，判断以i为中心的回文字符串长度为多少，因为回文有奇偶之分，所以要分开判断

class Solution {int start=0,maxLength=0;public String longestPalindrome(String s) {if(s.length()<2)return s;for(int i=0;i<s.length();i++){searchPalindrom(s,i,i);searchPalindrom(s,i,i+1);}return s.substring(start,maxLength+start);}private void searchPalindrom(String s,int left,int right) {// TODO Auto-generated method stubwhile(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}if(maxLength<right-left-1){start=left+1;maxLength=right-left-1;}}
}

Runtime: 8 ms, faster than 99.44% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 38 MB, less than 61.92% of Java online submissions for Longest Palindromic Substring.

解法二

中心思想与解法一类似，但是不用子函数

public String longestPalindrome(String s) {if(s.length()<2)return s;int n=s.length(),maxLength=0,start=0;for(int i=0;i<n;){if((n-i)<maxLength/2)break;int left=i,right=i;while(right<n-1&&s.charAt(right+1)==s.charAt(right))right++;i=right+1;while(left>0&&right<n-1&&s.charAt(right+1)==s.charAt(left-1)){left--;right++;}if(maxLength<right-left+1){start=left;maxLength=right-left+1;}}return s.substring(start,maxLength+start);}

Runtime: 7 ms, faster than 99.69% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 37.7 MB, less than 86.70% of Java online submissions for Longest Palindromic Substring.

解法三

 public String longestPalindrome(String s) {if(s.length()<2)return s;boolean[][] dp=new boolean[s.length()][s.length()];int length=0,left=0,right=0;for(int i=0;i<s.length();i++){for(int j=0;j<i;j++){if(s.charAt(i)==s.charAt(j)&&(i-j<2||dp[j+1][i-1]))dp[j][i]=true;if(dp[j][i]&&length<i-j+1){length=i-j+1;left=j;right=i;}}dp[i][i]=true;}return s.substring(left,right+1);}

Runtime: 42 ms, faster than 47.18% of Java online submissions for Longest Palindromic Substring.
Memory Usage: 39.1 MB, less than 24.27% of Java online submissions for Longest Palindromic Substring.
还有一种马拉车算法没品明白，二刷再来品品吧

这篇关于*LeetCode——Longest Palindromic Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---