字符串的基本递归队列

Question

我有一些在字符数组中创建字符串的规则

a. The string begins with an 'a'
b. Each 'a' is followed by nothing or an 'a' or "bb"
c. Each "bb" is followed by nothing or an 'a'

我的代码是：-

    bool checkAB(char input[]) {
        if(input[0]=='[=11=]'){
            return true;
        }
        if(input[0]!='a'){
            return false;
        }
        bool ans=checkAB(input+1);
        if(input[0]=='a'){
            if(input[1]=='a' || (input[1]=='b' && input[2]=='b') || input[1]==' ')
                return ans && true;
    
            if(input[1]=='b' && input[2]=='b'){
                if(input[3]==' ' || input[3]=='a'){
                    return ans && true;
                }
            }
        }
    
        
        return false;
    }

此代码未通过所有测试用例。谁能帮忙。请使用递归方法

Answer 1

考虑用“abb”调用时会发生什么

第一次调用会执行这一行：

bool ans=checkAB(input+1);

这意味着我们用输入“bb”调用函数

这将 return 错误（由于 if(input[0]!='a')）。

所以在第一次调用中我们将 ans 设置为 FALSE，因此我们最终 returning FALSE。

我认为在递归调用之前，您应该删除 'a'.

之后的任何“bb”

类似于：

bool checkAB(const char input[]) 
{
    if(input[0] != 'a') return false;   // input must start with an 'a'

    if (input[1] == '[=11=]') return true;  // input was "a"

    if (input[1] == 'b' && input[2] == 'b')
    {
        if (input[3] == '[=11=]') return true;   // input was "abb"
        
        return checkAB(input+3);  // Call without leading "abb"
    }

    return checkAB(input+1);  // Call without leading "a"
}

或者您可以使用 strcmp，例如：

bool checkAB(const char input[]) 
{
    if (input[0] != 'a') return false;
    
    if (strcmp(input, "a") == 0) return true;
    if (strcmp(input, "abb") == 0) return true;

    if (input[1] == 'b' && input[2] == 'b') return checkAB(input+3);  // Call without leading "abb"

    return checkAB(input+1);  // Call without leading "a"
}

Answer 2

对于初学者来说，函数参数应该有限定符 const，因为传递的字符串在函数中没有被改变

bool checkAB( const char input[]) {

空字符串不满足要求。所以这个 if 语句

    if(input[0]=='[=11=]'){
        return true;
    }

不正确。

因此调用

bool ans=checkAB(input+1);

可以将变量 ans 设置为 false，例如当源字符串为 "a" 时。在这种情况下，函数 returns false.

还不清楚为什么要将字符串的元素与 space 字符进行比较

 if(input[1]=='a' || (input[1]=='b' && input[2]=='b') || input[1]==' ')
                                                         ^^^^^^^^^^^^^

函数如下面的演示程序所示。

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

bool checkAB( const char *s ) 
{
    return  *s == 'a' && 
            ( *++s == '[=14=]' || 
              ( *s == 'a' && checkAB( s ) ) ||
              ( *s == 'b' && *++s == 'b' && ( ( *++s == '[=14=]' ) || ( *s == 'a' && checkAB( s ) ) ) ) );
}

int main(void) 
{
    const char *s = "a";
    
    printf( "\"%s\" -> %s\n", s, checkAB( s ) ? "true" : "false" );
    
    s = "aa";
    
    printf( "\"%s\" -> %s\n", s, checkAB( s ) ? "true" : "false" );

    s = "abb";
    
    printf( "\"%s\" -> %s\n", s, checkAB( s ) ? "true" : "false" );
    
    s = "aaa";
    
    printf( "\"%s\" -> %s\n", s, checkAB( s ) ? "true" : "false" );

    s = "abba";
    
    printf( "\"%s\" -> %s\n", s, checkAB( s ) ? "true" : "false" );
    
    return 0;
}

程序输出为

"a" -> true
"aa" -> true
"abb" -> true
"aaa" -> true
"abba" -> true

字符串的基本递归队列

basic resursion que of string

c

recursion

c-strings

function-definition