代码之家 › 专栏 › 技术社区 › sagi

C递归检查回文

recursion c

sagi · 技术社区 · 8 年前

我有一个赋值,我需要检查给定的字符串是否是回文或不是递归的。

例如:

aD1Da // returns 1
asd1s // returns 0

函数签名需要如下所示:

int isPolindrom(char str[]);

这意味着我只得到一个参数。我设法使用静态变量构建了一个解决方案(该函数将被多次调用,因此我们被指示不要使用静态变量,尽管我的解决方案适用于多个调用)。

我的解决方案:

static flag = 0; 
int isPolindrom(char str[])
{
    static int pos = 1;
    if (flag == 1) { 
        pos = 1; // Reset
        flag = 0; // Reset
    }
    if (pos >= strlen(str)) { 
        flag = 1; 
        return 1; 
    }
    if (*str == *(str + strlen(str) - pos)) { 
        pos++; 
        return  isPolindrom(str + 1); 
    }
    else return 0; 
}

也可以使用辅助函数,但我想知道是否以及如何才能做到这一点没有静态变量和没有编写辅助函数。

在自动测试中,他们将字符串作为常量字符串发送给我。例如:

isPolindrom("abcba")

3 回复 | 直到 8 年前

Community Mohan Dere 5 年前

是的,这是可能的。假设 字符串以null结尾并且是可变的 我们会这样做的

int isPolindrom(char s[])
{
    
    int l = 0;
    while(s[l]) l++;
    if(l == 2)
       return s[0]==s[1];
    if(l <= 1)
       return 1;

    char c=s[l-1];
    s[l-1]=0;
    
    int result = (s[0]==c) && isPolindrom(s+1);
    
    s[l-2]=c;
    return result ;
}

虽然它不会更改传递的参数,但我们正在内部修改它。这就是为什么需要修改sting要求的原因。

编辑后:

注意,我之前的回答是考虑到您不能使用任何函数,但正如OP明确指出的那样,我们可以轻松使用标准库函数,如 malloc 这就是为什么这个解决方案使用动态分配的内存。

使用给定的约束

int isPolindrom(const char *s)
{
    int l = 0;
    while(s[l]) l++;
    if(l == 2)
      return s[0]==s[1];
    if(l == 1)
      return 1;
    
    char *ss =  malloc(l-1);
    if( ss == NULL ){
       perror("Error in malloc");
       exit(EXIT_FAILURE);
    }
    for(int i=0;i<l-2;i++)
    ss[i]=s[i+1];
    ss[l-2]=0;
    int p = (s[0]==s[l-1]) && isPolindrom(ss);
    
    free(ss);
    return p;
}

Gaurav Sehgal 8 年前

在内部创建新字符串 palindrome() .

int palindrome(char *str)
{ 
    int len= strlen(str);
    if(len<=1)
      return true;
    char a=str[0];
    char b=str[len-1];
    char *newstr=malloc(len-2+1);
    for(int i=1;i<len-1;i++)
        newstr[i-1] = str[i];
    newstr[len-2]='\0';

    int res = (a==b && palindrome(newstr));
    free(newstr);
    return res;
}

并称之为

 palin("abcba");

CIsForCookies 8 年前

这是我的看法:

检查字符串是否必须是回文(即少于2个字符),如果是-返回true
如果没有,请检查 first == last ,如果是-使用内部字符串递归调用

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

bool is_palindrome(char * str){
    // end conditions
    if (!str)
        return false;
    if (strlen(str) < 2)
        return true;

    // check first vs. last
    if (str[0] == str[strlen(str) - 1]){
        // remove first & last chars (copy to array to allow this)
        char tmp_arr[strlen(str) - 1];
        strncpy(tmp_arr, str+1, strlen(str) - 2);
        tmp_arr[strlen(str) - 2] = '\0';
        return is_palindrome(tmp_arr);

        /* if string was mutable - this would be easier:

                str[strlen(str) - 1] = '\0';
                return is_palindrome(str + 1);
        */
    }

    return false;
}

int main(){
    printf(is_palindrome("abcddcba") ? "true\n" : "false\n");
    printf(is_palindrome("abcddcbaa") ? "true\n" : "false\n");
    printf(is_palindrome("abcd   dcba") ? "true\n" : "false\n");
    while(1);
    return 0;
}