C++算法简单的递归回文检查器

Question

我写了一个字符串回文检查器,我的导师说它比它需要的更复杂.我已经阅读了类似的线程并且用谷歌搜索了,但我完全不知道如何使用比这更少的步骤来使用...

void isPal(string str){
int length = str.length();
if(length <= 1) cout << "Palindrome" << endl;//check for zero or one digit numbers
else if(str.at(0) == str.at(length -1)) {
    str = str.substr(1, (length - 2));
    isPal(str);}
else cout << "Not a palindrome." << endl;{
    cin >> str;}

Answer 1

使用递归

如果您仍想使用递归,请执行以下操作:

bool isPal(const string &str, int start, int end)
{
    if (start >= end)   
        return true;
    if (str[start] != str[end])
        return false;
    return isPal(str, ++start, --end);   
}

并打电话给isPal(str, 0, str.length()-1)主体.我们的想法是使用两个索引并移动它们,因为您不希望substr()每次都使用递归.

没有递归

实际上这个问题很容易做到,不使用递归,如下所示:

bool isPal(const string &str)
{
    int start=0, end=str.length()-1;
    while (start < end) {
        if (str[start++] != str[end--]) 
            return false;
    }
    return true;
}

Answer 2

检查一下：

int is_pal(int start, int end, string &str)
{
    if (start >= end)
        return 1;
    if (str[start] != str[end])
        return 0;
    return is_pal(++start, --end, str);   
}

从main调用方法。让我知道是否有帮助.. :)