5 Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analysis

1.How do we check a palindrome

1) using stack

2.Long palindrome include short palindrome

3.n-size String have n types of substring length.

solution 1

    public String longestPalindrome(String s) {

        int lenOfStr = s.length();
        int count = lenOfStr;

        //O(N^3)
        while(count > 0){//-->O(N)

            for(int i=0; i+count-1 < lenOfStr; i++) {//----->O(N/2)
                String subStr = s.substring(i,i+count);
                if(isPalindrome(subStr)) return subStr;//------>O(N/2)
            }
            count--;
        }

        return "";

    }
    private boolean isPalindrome(String s) {
        int lenOfStr = s.length();
        for(int i=0; i<lenOfStr/2; i++) {
            if(s.charAt(i) != s.charAt(lenOfStr-i-1)) return false;
        }
        return true;
    }

复杂度O(N^3)

Solution: better

定位中点，往两头分别找

public String longestPalindrome(String s) {

        int lenOfStr = s.length();
        if(lenOfStr == 0) return "";
        if(lenOfStr == 1) return s;

        String longestSoFar = "";
        for(int i=0; i < lenOfStr; i++) {

            //odd pld
            char center = s.charAt(i);
            int left = i;
            int right = i;

            while(left >= 0 && right <= lenOfStr-1) {
                if(s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                }
                else break;
            }

            //adjust left&right
            left++;
            right--;
            //generate this palindrome
            String thisPalindrome = s.substring(left, right+1);

            //check whether it is longer than longestSoFar
            if(thisPalindrome.length() > longestSoFar.length()) longestSoFar = thisPalindrome;

        }

        //even
        for(int i=0; i < lenOfStr-1; i++) {
            if(s.charAt(i) == s.charAt(i+1)) {
                int left = i;
                int right = i+1;

                while(left >= 0 && right <= lenOfStr-1) {
                    if(s.charAt(left) == s.charAt(right)) {
                        left--;
                        right++;
                    }
                    else break;
                }

                //adjust left&right
                left++;
                right--;
                //generate this palindrome
                String thisPalindrome = s.substring(left, right+1);

                //check whether it is longer than longestSoFar
                if(thisPalindrome.length() > longestSoFar.length()) longestSoFar = thisPalindrome;
            }
        }

        return longestSoFar;
    }

O(N^2)