Created
April 8, 2016 00:02
-
-
Save hornd/0eb46cbaed90da93e63405b78310fca5 to your computer and use it in GitHub Desktop.
Longest palindromic subsystem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public String longestPalindrome(String ss) { | |
if (ss == null) { | |
return null; | |
} | |
if (ss.length() == 1) { | |
return ss; | |
} | |
String longest = ss.substring(0, 1); | |
for(int i=0; i<ss.length(); i++) { | |
String centeredAtI = getSubstringFor(ss, i, i); | |
if (centeredAtI.length() > longest.length()) { | |
longest = centeredAtI; | |
} | |
String centeredAfter = getSubstringFor(ss, i, i+1); | |
if (centeredAfter.length() > longest.length()) { | |
longest = centeredAfter; | |
} | |
} | |
return longest; | |
} | |
public String getSubstringFor(String s, int begin, int end) { | |
while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)) { | |
begin--; | |
end++; | |
} | |
return s.substring(begin + 1, end); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment