Welcome~~~


Another blog:
http://fun-st.blogspot.com/

It is easier to write an incorrect program than understand a correct one.

Friday, February 25, 2011

Match sub-string within a string with tolerance of 1 character mismatch - Stack Overflow

Match sub-string within a string with tolerance of 1 character mismatch - Stack Overflow

Question - Amazon Interview Quesion

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

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


A more 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);


No comments:

Post a Comment