Longest Palindromic Substring
Leetcode #5 | Medium | Расширение из центра
Идея
Идея расширения из центра и центром может быть либо i,i либо i,i+1
Big-O
- Время
O(N^2) - Память
O(1)
Код
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String p1 = expand(s, i, i);
String p2 = expand(s, i, i + 1);
if (p1.length() > res.length()) res = p1;
if (p2.length() > res.length()) res = p2;
}
return res;
}
private String expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return s.substring(l + 1, r);
}
}