匹配字符串中的子字符串，容差为 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 == '' )
        return 1;

    if ( *str == '' )
        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) == '' )
            return 1;
        else
            return 0;
    }
}

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

    return ok;
}


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

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

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

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