2014年5月13日星期二

Loop Solution - Longest Palindromic Substring **

The idea is to loop the String, for each char to find the longest palindrome, case 1 center is one letter and case 2 is that center is another two letters are equal.

Some questions need to be clarified: like lower case upper case, like space or other specials

public class Solution {
    public String longestPalindrome(String s){
        if(s == null || s.length() == 0){
            return s;
        }
        int maxLength = 0;
        String maxString = null;
        int i  = 0;
        while(i < s.length()){
            int curLength = 1;
            int next = i + 1;
            int prev = i - 1;
            while(prev >= 0 && next < s.length()){
                if(s.charAt(prev) == s.charAt(next)){
                    curLength = curLength + 2;
                    next++;
                    prev--;
                }else{
                    break;
                }
            }
            if(curLength > maxLength){
                maxLength = curLength;
                if(next > s.length()){
                    next = s.length();
                }
                maxString = s.substring(prev + 1, next);
            }
            //case 2: even palidrome
            if(i + 1 < s.length() && s.charAt(i + 1) == s.charAt(i)){
                prev = i - 1;
                next = i + 2;
                curLength = 2;
                while(prev >= 0 && next < s.length()){
                    if(s.charAt(prev) == s.charAt(next)){
                        curLength = curLength + 2;
                        next++;
                        prev--;
                    }else{
                        break;
                    }
                }
                if(curLength > maxLength){
                    maxLength = curLength;
                    maxString = s.substring(prev + 1, next);
                }
            }
            i++;
        }
        return maxString;
    }
}

没有评论: