Java回文串檢查函數優化思路分享

在Java中，檢查一個字符串是否為回文串（即正讀和反讀都相同的字符串）是一個常見的需求。下面是一個優化的回文串檢查函數，并附帶一些優化思路的分享。

優化思路

1. 雙指針法：這是最常用的方法之一。通過使用兩個指針，一個從字符串的開頭開始，另一個從字符串的末尾開始，逐個比較字符，直到兩個指針相遇或交叉。這種方法的時間復雜度是O(n)，空間復雜度是O(1)。

2. 棧或隊列：使用棧或隊列來存儲字符串的一半，然后與另一半進行比較。這種方法的時間復雜度也是O(n)，但空間復雜度是O(n)。

3. 遞歸：使用遞歸方法檢查回文串。這種方法的時間復雜度是O(n)，但空間復雜度較高，因為遞歸調用棧的深度是n。

4. 字符串反轉：將字符串反轉后與原字符串比較。這種方法的時間復雜度是O(n)，空間復雜度是O(n)。

優化后的代碼示例

下面是一個使用雙指針法的優化回文串檢查函數：

public class PalindromeChecker {

    public static boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("racecar")); // true
        System.out.println(isPalindrome("hello"));    // false
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
    }
}

代碼解釋

1. 邊界條件處理：首先檢查字符串是否為空或長度為0，如果是則直接返回true。
2. 雙指針初始化：初始化兩個指針，left指向字符串的開頭，right指向字符串的末尾。
3. 循環比較：在left小于right的情況下，逐個比較兩個指針所指向的字符。如果發現不相等的字符，則返回false。否則，移動指針繼續比較。
4. 返回結果：如果循環結束沒有發現不相等的字符，則返回true。

總結

通過使用雙指針法，我們可以在O(n)的時間復雜度和O(1)的空間復雜度內完成回文串檢查。這種方法簡單高效，適用于大多數情況。其他方法如棧、隊列、遞歸和字符串反轉雖然也有其應用場景，但在大多數情況下，雙指針法是最佳選擇。