如何在Java中優化回文串算法

在Java中，有多種方法可以優化回文串算法

1. 使用雙指針法： 這種方法的基本思想是從字符串的兩端開始，逐個比較字符是否相等。如果遇到不相等的字符，則返回false。如果遍歷完整個字符串都沒有發現不相等的字符，那么這個字符串就是回文串。這種方法的時間復雜度為O(n)，空間復雜度為O(1)。

public 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;
}

2. 反轉字符串后比較： 這種方法的基本思想是將輸入的字符串反轉，然后與原字符串進行比較。如果反轉后的字符串與原字符串相等，那么這個字符串就是回文串。這種方法的時間復雜度為O(n)，空間復雜度為O(n)。

public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    String reversed = new StringBuilder(s).reverse().toString();
    return s.equals(reversed);
}

3. 使用棧： 這種方法的基本思想是將字符串的一半字符壓入棧中，然后與剩余的字符進行比較。如果所有字符都相等，那么這個字符串就是回文串。這種方法的時間復雜度為O(n)，空間復雜度為O(n)。

public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length() / 2; i++) {
        stack.push(s.charAt(i));
    }
    for (int i = s.length() - 1; i >= 0; i--) {
        if (stack.pop() != s.charAt(i)) {
            return false;
        }
    }
    return true;
}

4. 使用隊列： 這種方法的基本思想是將字符串的一半字符放入隊列中，然后與剩余的字符進行比較。如果所有字符都相等，那么這個字符串就是回文串。這種方法的時間復雜度為O(n)，空間復雜度為O(n)。

import java.util.LinkedList;
import java.util.Queue;

public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    Queue<Character> queue = new LinkedList<>();
    for (int i = 0; i < s.length() / 2; i++) {
        queue.offer(s.charAt(i));
    }
    for (int i = s.length() - 1; i >= 0; i--) {
        if (!queue.offer(s.charAt(i))) {
            return false;
        }
        if (!queue.poll() == s.charAt(i)) {
            return false;
        }
    }
    return true;
}

5. 使用HashMap： 這種方法的基本思想是將字符串的字符及其出現次數存儲在HashMap中，然后檢查HashMap中的字符是否滿足回文串的條件。這種方法的時間復雜度為O(n)，空間復雜度為O(n)。

import java.util.HashMap;
import java.util.Map;

public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    int oddCount = 0;
    for (int count : map.values()) {
        if (count % 2 != 0) {
            oddCount++;
        }
        if (oddCount > 1) {
            return false;
        }
    }
    return true;
}

總結：在這些方法中，雙指針法是最優的，因為它的時間復雜度最低（O(n)），空間復雜度也最低（O(1)）。其他方法雖然在某些情況下也可以實現回文串的判斷，但它們的時間和空間復雜度相對較高。