判定字符串是否为回文
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个由多个a字符和b字符组成的字符数组。字符串中有一个特殊的字符X位于串的正中间（例如，ababa...ababXbabab..baaa）。如何判定该字符串是否为回文？
核心思路
由于中间元素是X，所以判断X前后两端字符串的元素是否回文即可。因此，将X前半段元素依次入栈，与X后半段的元素对比，若元素全部相同，即为回文字符串，否则不是回文字符串。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 判断字符串是否为回文字符串
*
* @className: IsPalindrome
* @author: Max Solider
* @date: 2023-06-08 22:45
*/public class IsPalindrome {
private static LLStack stack = new LLStack();
/**
* 判断字符串是否回文
* @param data 字符串
* @return 是否回文
*/
public static boolean isPalindrome(char[] data) {
boolean flag = false;
for (char c : data) {
if (c == 'X') {
flag = true;
continue; }
if (!flag) {
stack.push(String.valueOf(c));
}
if (flag) {
if (!stack.pop().equals(String.valueOf(c))) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
char[] data = "ababababaXababbabaa".toCharArray();
System.out.println("The result of isPalindrome is :" + isPalindrome(data));
data = "ababababaXababababa".toCharArray();
System.out.println("The result of isPalindrome is :" + isPalindrome(data));
}
}
时间复杂度
时间复杂度为O(n)，用于扫描长度为n的链表。
空间复杂度
空间复杂度为O(n)，用于存储字符串前半段元素。