-
Notifications
You must be signed in to change notification settings - Fork 0
/
LongestPalindromicSubstring.java
39 lines (37 loc) · 1.39 KB
/
LongestPalindromicSubstring.java
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
/*
* https://leetcode.com/problems/longest-palindromic-substring/
*/
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) {
return s;
}
String max = s.substring(0, 1);
for (int i = 1 ; i < s.length() ; i++) {
StringBuilder stringBuilder = new StringBuilder(s);
String s1 = stringBuilder.insert(i, s.charAt(i)).toString();
int halfPalindromeLength = halfPalindromeLength(s, i);
if ((halfPalindromeLength << 1) + 1 > max.length()) {
max = s.substring(i - halfPalindromeLength, i + halfPalindromeLength + 1);
}
int halfPalindromeLength1 = halfPalindromeLength(s1, i);
if ((halfPalindromeLength1 << 1) > max.length()) {
max = s.substring(i - halfPalindromeLength1, i + halfPalindromeLength1);
}
}
return max;
}
private int halfPalindromeLength(String s, int index) {
int i = 1;
while (i != index + 1 && i + index != s.length()) {
if (s.charAt(index - i) != s.charAt(index + i)) {
return i - 1;
}
i++;
}
return i - 1;
}
public static void main(String[] args) {
System.out.println(new LongestPalindromicSubstring().longestPalindrome("babad")); // bab
}
}