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

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

问题如下:

在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); 

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

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

 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的每个后缀执行此操作的函数。

这与IT的经典问题有关,称为Levenshtein距离 。 有关不同语言的一系列实现,请参阅Wikibooks 。

这与早期的解决方案略有不同,但我对此问题很感兴趣,并希望尝试一下。 显然,如果需要优化,我只想要一个解决方案。

 char *match(char *str, char *substr, int tolerance) { if (! *substr) return str; if (! *str) return NULL; while (*str) { char *str_p; char *substr_p; char *matches_missing; char *matches_mismatched; str_p = str; substr_p = substr; while (*str_p && *substr_p && *str_p == *substr_p) { str_p++; substr_p++; } if (! *substr_p) return str; if (! tolerance) { str++; continue; } if (strlen(substr_p) <= tolerance) return str; /* missed due to a missing letter */ matches_missing = match(str_p, substr_p + 1, tolerance - 1); if (matches_missing == str_p) return str; /* missed due to a mismatch of letters */ matches_mismatched = match(str_p + 1, substr_p + 1, tolerance - 1); if (matches_mismatched == str_p + 1) return str; str++; } return NULL; } 

问题是有效地做到这一点吗?

天真的解决方案是从左到右循环遍历str中size substr每个子字符串,如果当前子字符串(如果只有一个字符在比较中不同)则返回true。

设n = str的大小设m = substr的大小

str中有O(n)个子串,匹配步骤需要时间O(m) 。 因此,天真的解决方案及时运行O(n*m)

随着没有。 公差水平。

适用于我能想到的所有测试用例。 松散地基于| / | ad的解决方案。

 #include #include report (int x, char* str, char* sstr, int[] t) { if ( x ) printf( "%s is a substring of %s for a tolerance[%d]\n",sstr,str[i],t[i] ); else printf ( "%s is NOT a substring of %s for a tolerance[%d]\n",sstr,str[i],t[i] ); } int find_with_tolerance (char *str, char *sstr, int tol) { if ( (*sstr) == '\0' ) //end of substring, and match return 1; if ( (*str) == '\0' ) //end of string if ( tol >= strlen(sstr) ) //but tol saves the day return 1; else //there's nothing even the poor tol can do return 0; if ( *sstr == *str ) { //current char match, smooth return find_with_tolerance ( str+1, sstr+1, tol ); } else { if ( tol <= 0 ) //that's it. no more patience return 0; for(int i=1; i<=tol; i++) { if ( *(str+i) == *sstr ) //insertioan of a foreign character return find_with_tolerance ( str+i+1, sstr+1, tol-i ); if ( *str == *(sstr+i) ) //deal with dletion return find_with_tolerance ( str+1, sstr+i+1, tol-i ); if ( *(str+i) == *(sstr+i) ) //deal with riplacement return find_with_tolerance ( str+i+1, sstr+i+1, tol-i ); if ( *(sstr+i) == '\0' ) //substr ends, thanks to tol & this loop return 1; } return 0; //when all fails } } int find (char *str, char *sstr, int tol ) { int w = 0; while (*str!='\0') w |= find_with_tolerance ( str++, sstr, tol ); return (w) ? 1 : 0; } int main() { const int n=3; //no of test cases char *sstr = "dog"; //the substr char *str[n] = { "doox", //those cases "xxxxxd", "xxdogxx" }; int t[] = {1,1,0}; //tolerance levels for those cases for(int i = 0; i < n; i++) { report( find ( *(str+i), sstr, t[i] ), *(str+i), sstr, t[i] ); } return 0; }