java中如何實現最長回文子串

這篇文章給大家分享的是有關java中如何實現最長回文子串的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

最長回文子串

給你一個字符串 s，找到 s 中最長的回文子串。

鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring

示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：
輸入：s = "cbbd"
輸出："bb"

示例 3：
輸入：s = "a"
輸出："a"

示例 4：
輸入：s = "ac"
輸出："a"

// 在評論區看到的解法，簡單易懂，效率高
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() ==1){
            return s;
        }
        // arr保存回文的起始下標和結束下標
        char[] arr = s.toCharArray();
        int[] res = new int[2];
        // 回文即是中間相同，左右對稱的字符串，先確定中間對稱的部分，再向兩邊擴展。
        for(int i=0;i<s.length();i++){
            i = funtion(arr,i,res);
        }
        return s.substring(res[0],res[1]+1);
    }
    
    public int funtion(char[] arr,int mid,int[] res){
        int start = mid;
        int end = mid;
        //1 確定中間相同的部分
        while(end<arr.length-1&&arr[start] == arr[end+1]){
            end++;
        }
        //定位中間部分的最后一個字符,i 跳躍到中間相同部分的末尾。
        int ans = end;
        
       	//2 從中間相同部分的邊界，向兩邊擴展
        while(start>0&&end<arr.length-1&&arr[start-1]==arr[end+1]){
            start--;
            end++;
        }
        //3 保留最長的回文
        if(end-start > res[1]-res[0]){
            res[0] = start;
            res[1] = end;
        }
        // 重點:很好的提高了效率
        return ans;
    }
}

感謝各位的閱讀！關于“java中如何實現最長回文子串”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！