Leetcode -- 5. Longest Palindromic Substring(Strategy)

5. Longest Palindromic Substring
medium
https://leetcode.com/problems/longest-palindromic-substring/#/description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思路： - iterate string, keep finding longer palindrome(curLen)
                  check if str[i-curlen-1, i]: curLen+=2
                  else if str[i-curlen, i]: curLen+=1

Complexity: Time O(n^2) for "aaaa..a" Space O(1)

public String longestPalindrome(String s) {
        //if ...*axxa (a), we check if *axxaa isPalindrome
        // else axxa(a)
        //else palindrome disconnect here
        //keep tracking current len to set begin, cuz if < current len, not longest, skip
        if(s.length() < 2)return s;
        String res = "";
        int curLen = 0;//watch index boundary
        for(int i = 1; i < s.length(); i++){
            if(isPalindrome(s, i-curLen-1, i)){
                res = s.substring(i-curLen-1, i+1);//susbstring
                curLen += 2; 
            }else if(isPalindrome(s, i-curLen, i)){
                res = s.substring(i-curLen,i+1);
                curLen += 1;
            }
        }
        return res;
    }
    public boolean isPalindrome(String s, int begin, int end){
        if(begin < 0)return false;
        while(begin < end){
            if(s.charAt(begin) == s.charAt(end)){
                begin++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }