如何使此递归函数检查字符串是否是回文？

Question

该函数应反转字符串，如果前后相同，则返回true。我必须为此使用递归，并且不能为此使用reverse()。我通过调试器运行了我的代码，当我检查s == reverse时，我的代码似乎返回false。

这是我的尝试：

bool Palindrome(const string& s, int i){
string reverse;

    if(i < s.size()){
        reverse[i] = s[s.size()-(i+1)]; // first character in reverse is the last character in s
        Palindrome(s, i + 1);
        }       
    if(s == reverse){
        return true;
    }
    else{
        return false;
    }

}

Answer 1

#include<string>
#include<iostream>


bool palindrome(const std::string& s, size_t && i=0){

    if(i < s.size()/2 && s[i] == s[s.size()-(i+1)])
        palindrome(s, std::move(++i));

    return i==s.size()/2.0 || s.size()<=1;
}


//Testing
int main(){
    std::cout<<palindrome("yhtthy");
    std::cout<<palindrome("yoy");
}

Answer 2

以下代码显示了您在问题中详述的示例实现。它使用递归创建一个反向字符串，然后将其与参考字符串进行比较，并返回布尔结果。

内存复杂度O（n）。但是实际上，反向字符串确实需要额外的O（n）内存。

#include <iostream>
#include <algorithm>
using namespace std;

bool isPalindrome(string& reference, string& reversed, int index){
    if(index >= reference.size()/2){
        return reference == reversed;
    }

    int lastIndex = reference.size()-1;
    swap(reversed[index], reversed[lastIndex-index]);
    return isPalindrome(reference, reversed, index+1);
}

int main() {
    string ref = "abcdcba";
    string test = ref;
    cout << isPalindrome(ref,test,0) << endl;
    return 0;
}