最长回文子串.力扣5

￡神魔★判官ぃ 2023-10-01 21:21 21阅读 0赞

## 一、题目描述 ##

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 二、思路 ##

1.暴力法： 定义两个指针直接遍历字符串，记录最长回文字串的长度和起始位置，返回最长回文子串

2.中心扩散：与暴力法不同的是，这次遍历字符串的时候从中心开始向两边遍历，返回最长回文子串

## 三、代码实现 ##

### 暴力法 ###

class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            //最长字串起始位置
            int begin = 0;
            //回文串的最大长度
            int maxLen = 1;
            //将字符串转换为char数组，非必要
            char[] charArray = s.toCharArray();
            //遍历字符串
            for(int i = 0;i < len - 1;i++){
                for(int j = i + 1;j < len;j++){
                    //如果时回文串且长度大于当前最大回文串长度
                    if(j - i + 1 > maxLen && voidChild(charArray,i,j)){
                        //更新长度
                        maxLen = j - i + 1;
                        //更新起始位置
                        begin = i;
                    }
                }
            }
            //返回截取的子串
            return s.substring(begin,begin+maxLen);
        }
        //判断是否为回文串,从两端遍历
        public boolean voidChild(char[] charArray,int left,int right){
            while(left < right){
                if(charArray[left] != charArray[right]){
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    }

### 中心扩散 ###

class Solution {
      public static String longestPalindrome(String s){
            //回文串的最大长度
            int maxLen = 1;
            //最长字串起始位置
            int begin = 0;
            //将字符串转换为char数组，非必要
            char[] charArray = s.toCharArray();
            for (int i = 0;i < s.length()-1;i++){
                //回文串中心是一个字符
                int oodLen = len(charArray,i,i);
                //回文串中心是两个字
                int evenLen = len(charArray,i,i+1);
                //回文串的最大长度
                int maxMLen = Math.max(oodLen,evenLen);
                if (maxMLen > maxLen){
                    maxLen = maxMLen;
                    begin = i - (maxLen-1)/2;
                }
            }
            //返回截取的子串
            return s.substring(begin,begin+maxLen);
        }
        public static int len(char[] charArray,int left,int right){
            //当left==right时，回文串中心是一个字符，长度为奇数
            //当left+1==right时，回文串中心是两个字符，长度为偶数
            int len = charArray.length;
            int i = left;
            int j = right;
            while (i >= 0 && j < len){
                if (charArray[i] == charArray[j]){
                    //向两边扩散遍历
                    i--;
                    j++;
                }else {
                    //不满足条件时停止
                    break;
                }
            }
            //跳出循环时，charArray[i] != charArray[j],回文串的长度是j - i + 1 - 2 = j - i -1
            return j - i - 1;
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/52ff0cf81d0d4281b985474fdbf2058a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16