5. Longest Palindromic Substring — Medium

前往題目

之前寫的文章

思路

1. 2 pointers
2. 每個index都當是中心點向左右擴散
3. 奇偶分開處理

Code

class Solution {
    public String longestPalindrome(String s) {
        int resL = 0, resR = 0;
        int resLen = resR - resL + 1;

        for (int i = 0; i < s.length(); ++i) {
            int l = i, r = i;

            //Odd situation
            while (inBound(r, l, s) && s.charAt(l) == s.charAt(r)) {
                // Check longer
                if (resLen < (r - l + 1)) {
                    resL = l;
                    resR = r;
                    resLen = r - l + 1;
                }

                // Move pointers
                --l;
                ++r;
            }

            // Reset pointers
            l = i;
            r = i + 1;

            // Even situation
            while (inBound(r, l, s) && s.charAt(l) == s.charAt(r)) {
                // Check longer
                if (resLen < (r - l + 1)) {
                    resL = l;
                    resR = r;
                    resLen = r - l + 1;
                }

                // Move pointers
                --l;
                ++r;
            }
        }

        return s.substring(resL, resR + 1);
    }

    private boolean inBound(int r, int l, String s) {
        return l >= 0 && r < s.length();
    }
}