最長回文子串_牛客網

描述

對于一個字元串，請設計一個高效算法，計算其中最長回文子串的長度。

給定字元串A以及它的長度n，請傳回最長回文子串的長度。

示例1

輸入：

"abc1234321ab",12      

傳回值：

分析

        此處使用一個雙指針的辦法解決問題，每次尋找目前位置的最長回文串，如果目前位置的回文串大于記錄值，則更新。需要注意的是此處應考慮數組越界問題，将奇數串和偶數串分開讨論。

import java.util.*;

public class Solution {
    int len = 0;
    public int getLongestPalindrome(String A, int n) {
        // write code here
        
        for(int i = 0; i < n; i++) {
            subLong(A,i,i);
        }
        for(int i = 0; i < n - 1; i++) {
            subLong(A,i, i+1);
        }
        return len;
    }
    
    public void subLong(String str, int start, int end) {
        while(start >= 0 && end < str.length() && (str.charAt(start) == str.charAt(end))) {
            len = Math.max(len,end-start+1);
            start--;
            end++;
            
        }
    }
}