回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，但”good”不是回文，试写一算法利用栈判定给定的字符序列是否为回文。（提示：将一半字符入栈）

1. 将字符串的前一半字符依次入栈，注意如果字符串长度为奇数，则中间的字符不需要入栈。
2. 从字符串的中间位置开始，依次比较栈顶元素和字符串剩余部分的字符，如果不相等则不是回文，如果相等则继续比较。
3. 如果栈为空并且比较完所有字符都相等，则是回文，否则不是回文。

代码实现如下：

bool isPalindrome(string s) {
    stack<char> st;
    int len = s.length();
    int mid = len / 2;
    for (int i = 0; i < mid; i++) {
        st.push(s[i]);
    }
    if (len % 2 == 1) {
        mid++;
    }
    for (int i = mid; i < len; i++) {
        if (st.empty() || st.top() != s[i]) {
            return false;
        }
        st.pop();
    }
    return st.empty();
}

相关问题

回文是指正读、反读均相同的字符序列，如"abba"和“abdba”均是回文。“good”不是回文。试设计算法判定给定的字符序列是否是回文

一个简单的判断回文的算法如下：

1. 从字符串的两端分别开始遍历，判断每个字符是否相等。

2. 如果在遍历过程中发现任何不相等的字符，就说明这个字符串不是回文。

3. 当左右两端的遍历相遇时，就说明这个字符串是回文。

下面是算法的Python代码实现：

def isPalindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

这个算法的时间复杂度是$O(n)$，其中$n$是字符串的长度。

回文是指正读和反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符串是否为回文。

算法如下：

1. 定义两个指针，一个指向字符串的开头，一个指向字符串的结尾。

2. 每次比较两个指针指向的字符是否相同，如果不同，则不是回文。

3. 如果相同，则将两个指针向中间移动，继续比较。

4. 当两个指针相遇时，说明字符串是回文。

代码实现：

bool isPalindrome(string s) {
    int left = , right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}