1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | public String longestPalindrome(String s) { if(s==null || s.length()==1)return s; if(s.length()==1||(s.length()==2&&s.charAt(0)==s.charAt(1)))return s; String maxPalindrome = null; int maxLen=0; ///no nneed to check first and last char for(int i=0;i<s.length();i++){ String p = palindromeLen(s,i); if(maxLen<p.length()){ maxLen=p.length(); maxPalindrome=p; } } return maxPalindrome; } String palindromeLen(String s, int i){ int left=i,right=i+1; String s1="",s2=""; while(left>=0&&right<s.length()){ if(s.charAt(left)==s.charAt(right)){ left--; right++; } else break; } if(left!=i) s1=s.substring(++left,right); left=i;right=i+2; while(left>=0&&right<s.length()){ if(s.charAt(left)==s.charAt(right)){ left--; right++; } else break; } if(left!=i) s2=s.substring(++left,right); return (s1.length()>s2.length()?s1:s2) ; } |
Quick tips or notes that probably reflects 20 percent of knowledge that usually does 80 percent of job.
Saturday, May 28, 2016
Longest Palidrolimic 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.
Method:
palindrome string can had even number of character, which is balanced from virtual middle. it can also be odd number of characters, which is balanced from its real middle character.
I want to check out the palindrome string at each position, so each position need to check both of above situations.
below s generic solution without thinking of the 1000 and unique longest pelindrome substring.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment