Java回文串算法復(fù)雜度分析與實(shí)踐

在Java中，回文串是指一個(gè)字符串從前往后讀和從后往前讀是相同的

1. 時(shí)間復(fù)雜度分析：

   • 遍歷字符串：O(n)，其中n是字符串的長(zhǎng)度。
   • 檢查回文串：O(n/2)，因?yàn)槲覀兛梢詮膬啥讼蛑虚g移動(dòng)，每次比較一個(gè)字符。在最壞的情況下，我們需要比較n/2個(gè)字符。

   綜合以上兩個(gè)步驟，回文串檢查算法的時(shí)間復(fù)雜度為O(n)。

2. 空間復(fù)雜度分析：

   • 我們只需要常數(shù)級(jí)別的額外空間來存儲(chǔ)臨時(shí)變量和結(jié)果。因此，空間復(fù)雜度為O(1)。

3. 實(shí)踐： 下面是一個(gè)簡(jiǎn)單的Java實(shí)現(xiàn)，用于檢查字符串是否為回文串：

public class PalindromeChecker {
    public static void main(String[] args) {
        String input = "racecar";
        System.out.println("Is the input a palindrome? " + isPalindrome(input));
    }

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

這個(gè)實(shí)現(xiàn)首先檢查輸入字符串是否為空或長(zhǎng)度為0，如果是，則直接返回true。接下來，我們使用兩個(gè)指針，一個(gè)從左邊開始，另一個(gè)從右邊開始。我們?cè)谘h(huán)中逐個(gè)比較這兩個(gè)指針?biāo)赶虻淖址?，如果它們不相等，則返回false。否則，我們將左指針向右移動(dòng)一位，右指針向左移動(dòng)一位，直到兩個(gè)指針相遇。在這種情況下，我們返回true，表示輸入字符串是回文串。