Programming

Leetcode-最大回文字串

Leetcode-最大回文字串

<解題>


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.next();

        String result = findPalindromeSubstring(inputStr);
        System.out.println(result);
    }

    public static String findPalindromeSubstring(String inputStr) {
        int maxLength = 0;
        String longestPalindrome = "";

        for (int i = 0; i < inputStr.length(); i++) {
            // 奇數長度的迴文,以 i 為中心
            String palindromeOdd = expandAroundCenter(inputStr, i, i);
            if (palindromeOdd.length() > maxLength) {
                maxLength = palindromeOdd.length();
                longestPalindrome = palindromeOdd;
            }

            // 偶數長度的迴文,以 i 和 i+1 為中心
            String palindromeEven = expandAroundCenter(inputStr, i, i + 1);
            if (palindromeEven.length() > maxLength) {
                maxLength = palindromeEven.length();
                longestPalindrome = palindromeEven;
            }
        }

        return maxLength > 1 ? longestPalindrome : "None";
    }

    public static String expandAroundCenter(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return str.substring(left + 1, right);
        //從 left 的下一個位置開始,到 right 位置之前(不包含 right 位置),所對應的字串,即為最終的迴文子字串
    }
}

Time: O(n^2) Space: O(n^2)