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

本文介绍了匹配字符串中的子字符串，容差为 1 个字符不匹配的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在 CareerCup 上浏览了一些亚马逊面试问题，遇到了这个有趣的问题，但我一直不知道该怎么做.我从 2 天以来一直在思考这个问题.要么我正在采取一种方法，要么它是一个真正难以编写的函数.

I was going through some Amazon interview questions on CareerCup, 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.