匹配字符串中的子字符串,容差为1个字符不匹配

Question

我在CareerCup.com上经历了一些亚马逊的采访问题,我偶然发现了一个有趣的问题,我无法弄明白该怎么做.自从2天以来我一直在考虑这个问题.无论是我采取的方式,还是一个真正难以写的功能.

问题如下:

在C中编写一个函数,可以查找字符串是否是另一个字符串的子字符串.请注意,应忽略一个字符的不匹配.

A mismatch can be an extra character: ’dog’ matches ‘xxxdoogyyyy’  
A mismatch can be a missing character: ’dog’ matches ‘xxxdgyyyy’ 
A mismatch can be a different character: ’dog’ matches ‘xxxdigyyyy’

问题中没有提到返回值,所以我假设函数的签名可以是这样的:

char * MatchWithTolerance(const char * str, const char * substr);

如果与给定规则匹配,则将指针返回到字符串中匹配子字符串的开头.否则返回null.

奖金

如果有人也可以找出一种通用的方法来对n进行公差而不是1,那么那就太棒了.在这种情况下,签名将是:

char * MatchWithTolerance(const char * str, const char * substr, unsigned int tolerance = 1);

感谢所有想要尝试并分享他们成功解决方案的人.

Answer 1

这似乎有效,如果您发现任何错误,请告诉我,我会尝试修复它们:

int findHelper(const char *str, const char *substr, int mustMatch = 0)
{
    if ( *substr == '\0' )
        return 1;

    if ( *str == '\0' )
        return 0;

    if ( *str == *substr )
        return findHelper(str + 1, substr + 1, mustMatch);
    else
    {
        if ( mustMatch )
            return 0;

        if ( *(str + 1) == *substr )
            return findHelper(str + 1, substr, 1);
        else if ( *str == *(substr + 1) )
            return findHelper(str, substr + 1, 1);
        else if ( *(str + 1) == *(substr + 1) )
            return findHelper(str + 1, substr + 1, 1);
        else if ( *(substr + 1) == '\0' )
            return 1;
        else
            return 0;
    }
}

int find(const char *str, const char *substr)
{
    int ok = 0;
    while ( *str != '\0' )
        ok |= findHelper(str++, substr, 0);

    return ok;
}


int main()
{
    printf("%d\n", find("xxxdoogyyyy", "dog"));
    printf("%d\n", find("xxxdgyyyy", "dog"));
    printf("%d\n", find("xxxdigyyyy", "dog"));
}

基本上,我确保只有一个字符可以不同,并运行为haystack的每个后缀执行此操作的函数.