递归布尔函数,用于检查字符串是否为回文结构

Question

编写递归布尔函数,如果字符串是回文,则返回1,否则返回0.

bool ispalindrome(char str[])

注意:函数必须是递归的(不是递归函数的包装器),它必须使用给定的(上面)签名并且不允许全局或静态变量,而且,我们不能"破坏"给定的字符串.

我的尝试:

bool ispalindrome(char str[]){
    bool res;
    if (*str == 0 || *(str + 1) == 0)
        return 1;
    else{
        res = ispalindrome(str + 1);

现在我陷入了困境,我想到了一个使用动态数组的辅助函数,该数组将删除原始字符串中的第一个和最后一个元素,并在递归调用中使用它,但我不认为这是预期的解决方案.

编辑:我已经取得了一些进展,但它不起作用:

bool ispalindrome(char str[]){
    bool res;
    int l = strlen(str);
    char t;
    if (*str == 0 || *(str + 1) == 0)
        return 1;
    else{
        t = str[l-1];
        str[l-1] = 0;
        res = ispalindrome(str + 1);
        if (res == 0)
            return 0;

        if (str[0] == str[l - 2])
            res =1;
        else 
            res=0;
        str[l] = t;
        return res;
    }
}

Answer 1

所以,你当前的代码几乎可以工作.我看到的唯一问题是,在一个案例中,您在还原字符串中的更改之前返回.此外,您的索引中有一个错误.

我们还要注意一些风格修复:

1. *(str + 1)真的应该str[1].它们是等价的,但后者是预期的.

2. 既然你已经计算过l = strlen(str),你可以将它用于你的第一个条件,因为它更具可读性.

3. 您还可以使用更长的变量名称.它们并不贵.

4. 就个人而言,我喜欢这样,如果您将空字符写入字符串,则使用空字符而不是0.那是'\0'.但那只是我.

和代码:

bool ispalindrome(char str[]){
    int l = strlen(str);

    // Recusive Base Case
    if (l == 0 || l == 1)
        return true;

    // Save the last character of the string
    char t = str[l-1];
    str[l-1] = '\0';

    // Recursive call on the substring
    bool res = ispalindrome(str + 1);

    // Now, this is where you messed up. Before we return,
    // we need to fix the string!
    str[l-1] = t;

    // If the recursive call thinks that it's not a palindrome,
    // then we won't disagree.
    if (res == false)
        return res;

    // Check the (current) first position of the string against the last
    // You had an off by one error here.
    return (str[0] == str[l - 1]);
}

我们可以对代码的运行时进行小的改进吗？

代码工作方式的一个令人讨厌的特性是我们将始终使用strlen(str) / 2递归调用.我们可以在一个例子中使代码运行得更快,例如"abracadabra",字符串的第二个字母导致回文测试失败.

加快速度的一种方法是在递归调用(str[0] == str[l - 1]) 之前进行测试.我们可以相当容易地实现它,它可能看起来像这样:

bool ispalindrome(char str[]){
    int length = strlen(str);

    // Recursive Base Case
    if (length == 0 || length == 1)
        return true;

    // Check our case.
    // Note that this is occuring __before__ the recursive call
    if (str[0] != str[length - 1])
        return false;

    // Save the last character of the string
    char t = str[length - 1];
    str[length - 1] = '\0';

    // Recursive call on the substring
    bool res = ispalindrome(str + 1);

    // We need to fix the string
    str[length - 1] = t;

    return res;
}

所有这一切都说......

我已经在stackoverflow上看了几次这个问题,而且我总是好奇教练正在寻找什么.通过将字符串长度作为附加参数传递来解决此问题的经典版本.通过这样做,我们节省了大量的工作.

到目前为止发布的每个解决方案(包括我的)都会调用strlen()每个递归调用.这意味着所有这些解决方案至少都是如此O(n^2).如果我们可以将长度传递给递归调用,我们可以很容易地解决问题O(n).这将极大地减少工作量.

此外,您还可以以尾递归方式编写代码.这可以允许编译器生成对处理器执行更好的代码.(基本上,它会将代码转换为for循环的样子).这非常有用,因为您对非常大的字符串上的堆栈空间不足感到担忧.

但是,由于教师的限制,我们不能做任何这些事情.这有点蹩脚.