使用java解决最长回文子串-Leetcode 第5题

使用java解决最长回文子串-Leetcode 第5题

首先分析题目———最长回文子串，我们可以把问题拆分成两部分，即字符串的最长回文串问题 和 子串问题。

1.1、最长回文串

在此之前，我们首先了解一下如何判断字符串为回文串

采用递归的方式判断字符串是否为回文串

 //high为字符串的长度 - 1，low为字符串的起点
    public boolean isPalindrome(String s,int low, int high){

        //Base Case
        if(high <= low){
            return true;
        }

        //Base Case
        else if(s.charAt(low) != s.charAt(high)){
            return false;
        }

        else{
            return isPalindrome(s, low + 1, high - 1);
        }

    }

一般思路判断是否为回文串

public  boolean isPalindrome(String s) {
        int left = 0;
        int right = newStr .length() - 1;
        while(left < right){

            if(newStr.charAt(left) != newStr.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

由上思路我们可以大致了解回文串的判断方法，不难看出，以上两种方式都是从两端向中间靠拢去判断是否为回文串（由两端向中心聚拢），但是我们若要求得最长的回文串，我们应该从字符串的中心入手，但是字符串的字符个数又分为奇数和偶数，因此我们可以写一个方法：寻找以字符串中心字符a（字符串字符个数为奇数）或者以字符串中心字符 a 和 b （字符串字符个数为偶数）的最长字符串，即 由中心向两端扩散

//判断以s[l] 和 s[r]最长的回文串，l和r如果相同的话，就是奇数字符串，不相同的话就是偶数字符串
    public static String isPalindrome(String s, int l, int r){

        //当遇到两个不相等的字符的时候跳出循环了，然后使用java的substance
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        //substring方法是左闭右开的，即截取以 l + 1 为起点，r - 1为终点的字符串
        return s.substring(l + 1, r);
    }

1.2、最长回文子串

我们直接循环遍历每个字符，找到以每个字符，以及每个字符和该字符的下一个字符为中心的最长回文串，比较即可。

public static String longestPalindrome(String s) {

        String res = "";

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

            String s1 = isPalindrome(s, i, i);

            String s2 = isPalindrome(s, i, i + 1);

           if(res.length() <= s1.length()){
                res = s1;
            }
            if(res.length() <= s2.length()){
                res = s2;
            }
        }
        return res;
    }