首页 > 代码库 > [leetcode] Longest Palindromic Substring
[leetcode] Longest Palindromic Substring
题目：（String）
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.
题解：自己先写了一个循环所有substring的，超时。
public class Solution { public String longestPalindrome(String s) { if(s.length()==0||s.length()==1||checkIsPalindrome(s)) return s; int len = s.length(); for(int i =len-1 ; i>=1 ;i--) { for(int j =0; j<=len-i; j++) { if(checkIsPalindrome(s.substring(j,j+i))) return s.substring(j,j+i); } } return s; } public boolean checkIsPalindrome(String s) { Stack<Character> stack = new Stack<Character>(); int len =s.length(); if(len%2==0) { for(int i=0;i<len/2;i++) { stack.push(s.charAt(i)); } for(int i=len/2;i<len;i++) { char temp = stack.pop(); if(temp!=s.charAt(i)) return false; } return true; } else { for(int i=0;i<len/2;i++) { stack.push(s.charAt(i)); } for(int i=len/2+1;i<len;i++) { char temp = stack.pop(); if(temp!=s.charAt(i)) return false; } return true; } }}
看了别人的方法：
第二种方法“是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙，例如aba是回文，abba也是回文，这两种情况要分情况考虑）往两边同时进 行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂 度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)。”引自Code ganker（http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html）
public class Solution { public String longestPalindrome(String s) { if(s.length()==0||s.length()==1) return s; String longest = s.substring(0,1); for(int i=0;i<s.length(); i++) { String temp = buildTheLargeSubstring(s,i,i); if(temp.length()>longest.length()) longest =temp; temp = buildTheLargeSubstring(s,i,i+1); if(temp.length()>longest.length()) longest =temp; } return longest; } public String buildTheLargeSubstring(String s, int begin, int end) { while(begin>=0&&end<=s.length()-1&&s.charAt(begin)==s.charAt(end)) { begin--; end++; } return s.substring(begin+1,end); }}
[leetcode] Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。