x

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);
    }
}
Left-click: follow link, Right-click: select node, Scroll: zoom
x