Java回文串算法复杂度分析与实践

在Java中，回文串是指一个字符串从前往后读和从后往前读是相同的

1. 时间复杂度分析：

   • 遍历字符串：O(n)，其中n是字符串的长度。
   • 检查回文串：O(n/2)，因为我们可以从两端向中间移动，每次比较一个字符。在最坏的情况下，我们需要比较n/2个字符。

   综合以上两个步骤，回文串检查算法的时间复杂度为O(n)。

2. 空间复杂度分析：

   • 我们只需要常数级别的额外空间来存储临时变量和结果。因此，空间复杂度为O(1)。

3. 实践： 下面是一个简单的Java实现，用于检查字符串是否为回文串：

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

这个实现首先检查输入字符串是否为空或长度为0，如果是，则直接返回true。接下来，我们使用两个指针，一个从左边开始，另一个从右边开始。我们在循环中逐个比较这两个指针所指向的字符，如果它们不相等，则返回false。否则，我们将左指针向右移动一位，右指针向左移动一位，直到两个指针相遇。在这种情况下，我们返回true，表示输入字符串是回文串。