与1个字符不匹配公差匹配字符串内的子串 [英] Match sub-string within a string with tolerance of 1 character mismatch

问题描述

我要通过一些CareerCup.com亚马逊面试问题，我碰到这个有趣的问题，我一直无法弄清楚如何做出来。我一直在想这个，因为2天。要么我正在遥远的办法，或它的一个真正的硬函数写。

I was going through some Amazon interview questions on CareerCup.com, and I came across this interesting question which I haven't been able to figure out how to do. I have been thinking on this since 2 days. Either I am taking a way off approach, or its a genuinely hard function to write.

问题如下：

C编写一个函数，可以发现，如果一个字符串是另一个的子串。注意，一个字符的失配
应该被忽略。

Write a function in C that can find if a string is a sub-string of another. Note that a mismatch of one character should be ignored.

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’

返回值没有在问题中提到，所以我想这个函数的签名可以是这样的：

The return value wasn't mentioned in the question, so I assume the signature of the function can be something like this:

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

如果存在与给定的规则匹配，则指针返回字符串中匹配的子的开始。否则返回NULL。

If there is a match with the given rules, return the pointer to the beginning of matched substring within the string. Else return null.

奖金

如果有人也能找出使公差为n，而不是1的通用方法，那么这将是刚刚辉煌。
在这种情况下，签名将是：

If someone can also figure out a generic way of making the tolerance to n instead of 1, then that would be just brilliant. In that case the signature would be:

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

感谢所有那些谁也尝试此，分享他们成功的解决方案。

Thanks to all those who would attempt this and share their successful solution.

推荐答案

这似乎工作，让如果你发现任何错误，我知道，我会尽力解决这些问题：

This seems to work, let me know if you find any errors and I'll try to fix them:

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"));
}

基本上，我确保只有一个字符可以不同，并运行，这是否在草堆的每一个后缀的功能。

Basically, I make sure only one character can differ, and run the function that does this for every suffix of the haystack.

这篇关于与1个字符不匹配公差匹配字符串内的子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！