如何在Java中優(yōu)化回文串算法

在Java中，有多種方法可以?xún)?yōu)化回文串算法

1. 使用雙指針?lè)ǎ?這種方法的基本思想是從字符串的兩端開(kāi)始，逐個(gè)比較字符是否相等。如果遇到不相等的字符，則返回false。如果遍歷完整個(gè)字符串都沒(méi)有發(fā)現(xiàn)不相等的字符，那么這個(gè)字符串就是回文串。這種方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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. 反轉(zhuǎn)字符串后比較： 這種方法的基本思想是將輸入的字符串反轉(zhuǎn)，然后與原字符串進(jìn)行比較。如果反轉(zhuǎn)后的字符串與原字符串相等，那么這個(gè)字符串就是回文串。這種方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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. 使用棧： 這種方法的基本思想是將字符串的一半字符壓入棧中，然后與剩余的字符進(jìn)行比較。如果所有字符都相等，那么這個(gè)字符串就是回文串。這種方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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. 使用隊(duì)列： 這種方法的基本思想是將字符串的一半字符放入隊(duì)列中，然后與剩余的字符進(jìn)行比較。如果所有字符都相等，那么這個(gè)字符串就是回文串。這種方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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： 這種方法的基本思想是將字符串的字符及其出現(xiàn)次數(shù)存儲(chǔ)在HashMap中，然后檢查HashMap中的字符是否滿(mǎn)足回文串的條件。這種方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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;
}

總結(jié)：在這些方法中，雙指針?lè)ㄊ亲顑?yōu)的，因?yàn)樗臅r(shí)間復(fù)雜度最低（O(n)），空間復(fù)雜度也最低（O(1)）。其他方法雖然在某些情況下也可以實(shí)現(xiàn)回文串的判斷，但它們的時(shí)間和空間復(fù)雜度相對(duì)較高。