How would one approach the following question:
We have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and "*"
We want to check if the first string match the pattern, where the ? means that every char (alphanumeric) is permitted in that position, while * allows to have a sequence of alphanumeric chars.
If I was asked this question in an interview, this would be how I would begin figuring out my algorithm. Note: the first two cases are just how I would arrive at the final answer, and they aren't actually a suitable answer until number 3.
I would start with the easy case which is where there is no '?' or '*'. I would do a scan of the search string until I hit the first character in the pattern string. At that point, go to the next character in the pattern string and see if it matches the next character in the search string. If it does, continue, otherwise move back to the beginning of the pattern string but keep the current position in the search string. When you run out of characters in the pattern string, then you have a match, if you run out of characters in the search string, you don't.
Then move to the case of a '?' character. Do the same algorithm as before, except when you hit a '?' in the pattern string, go ahead and skip the current position in the search string and get the next character in the pattern string. Continue as you did in case 1.
Then move to the final case of '?' and '*' permitted. Do the same as the other two cases, except this time when you hit a '*', immediately find the next character after the '*' in the pattern string. Then scan the search string to find that next character. If you find it, keep going with case 1 & 2, when you are out of pattern characters you have a match. If you run out of search string characters, go to the next instance in the search string of the character immediately after the '*' in the pattern string and try again. If you still haven't found it at this point, then you could have had a false alarm with the very first match. So, start at the point where you started your last match check and do this whole process over again. When you hit the end of the search string, you don't have a match.
At this point, you have solved the problem. The solution is O(n) in most cases, but the worst case could be O(n^2)
If I had to actually solve this problem I'd probably just transform the pattern into a regular expression pattern by replacing * with [A-Za-z0-9]* and ? with [A-Za-z0-9] then use regex to match the string against the pattern.
For interview I'd probably then go on to give an answer like Jonathan's as I guess that is what they are looking for
I'd just call the function. fnmatch(3) (POSIX.2; on other platforms I'd just dig it from some posix emulation library). Most other language besides C/C++ have such function too.
If the interviewer wasn't happy with that answer, I'd count it against the company for deciding whether they made the review.
If the interviewer liked the answer, but asked about implementing that function, there is:
simple recursive variant (using arbitrary pseudo-code) (O(mn) worst):
bool matches(string:string, pattern:string):
if pattern[0] == '*':
# assuming || short-circuits this order is the faster on average
return matches(string, pattern[1:]) || matches(string[1:], pattern)
elseif pattern[0] == '?' or pattern[0] == string[0]:
return matches(string[1:], pattern[1:])
else:
return False
the complicated variant compiling the finite automaton (O(n) in time traded for higher space complexity for the automaton/time complexity of the preprocess, which I think is O(m2), but am too lazy to derive precisely right now).
Pragmatic approach:
? with \w and * with \w* or \w+I'm going to take a crack at this solution. Jonathan has the general gist of it, but I saw a possible problem and I like the challenge of attempting a solution myself.
This solution is assuming of course that regular expressions are not an option. Regular expressions exist expressly to match tricky patterns like this in an efficient manner, and I'm a strong believer in programmers writing modular libraries which do one thing and one thing well, and all other programmers using that library rather than re-invent the wheel.
My take on this is that * creates an interesting situation where a number of solutions become possible and not just one. In order to check the matching string for all these possibilities, you must quite literally check for all these possibilities. To give an example, I could have pattern a*bc to match azbbc, and if you assume the b following the z belongs to the section after the *, you don't match what would otherwise be a match. Likewise, if you didn't assume the b following the z to belong to the section after the *, then you no longer match azbc.
So a simplified version of the algorithm is the following (implementation can be seen here):
function search(matchString, pattern) {
var i = 0;
// For each character in matchString and pattern
for(; i<matchString.length && i<pattern.length; i++) {
if(pattern[i] === '*') {
// Star! If pattern has been valid up to now, then
// only one match must be valid after the *, so pass responsibility
// to searchStar.
var subMatchString = matchString.substring(i, matchString.length);
var subPattern = pattern.substring(i+1, pattern.length);
return searchStar(subMatchString, subPattern);
} else if (pattern[i] !== '?') {
// If it isn't * and it isn't ?, then compare characters.
// If characters don't match, we know it isn't valid.
if(matchString[i] !== pattern[i]) {
return failure(matchString, pattern);
}
} // else if (pattern[patternIndex] === '?') {
// Ignore '?'.. move along
//}
}
if(i === pattern.length) {
return success(matchString, pattern); // pattern exhausted
} else {
return failure(matchString, pattern); // matchString ended with unmatched pattern
}
}
// This function is called when star is encountered in pattern and
// pattern thus far is correct. This applies search on remaining
// match string and returns true if even one proves true.
function searchStar(matchString, pattern) {
while(matchString.length > 0) {
if(search(matchString, pattern)) {
return true;
}
matchString = matchString.substring(1, matchString.length);
}
return failure(matchString, pattern);
}
Efficiency can probably be improved by doing little things like ignoring duplicated "*"s and things of that sort, but I tried to keep it as simple as possible so that the reader can understand the general idea.
Hope that helps!
Here's a naive, but tested and working implementation using recursion. I think its O(n^3) because of the three cases on the asterik. There a decent number of corner cases in this problem.
Dr. Dobbs has a decent writeup on this problem: http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888
Though one of the comments hinted at using Boyer-Moore, it doesn't look like regular Boyer-Moore supports wildcards. There's a blog post that added wildcards to KMP string search - http://0x7fffffff.blogspot.com/2012/07/kmp-supporting-wild-card.html
from collections import namedtuple
import string
import unittest
LITERAL_CHARS = set(string.ascii_letters + string.digits)
def simple_matcher(pattern, string):
if pattern == "":
if string == "":
return True
else:
return False
# We have a non-empty pattern
else:
if string == "":
# If we only have * in the pattern, we can match the empty string.
if all(p == "*" for p in pattern):
return True
else:
return False
# We have a non-empty pattern and string
else:
if pattern[0] in LITERAL_CHARS:
return (pattern [0] == string [0]
and simple_matcher(pattern[1:], string[1:]))
elif pattern[0] == "?":
return simple_matcher(pattern[1:], string[1:])
elif pattern[0] == "*":
return (
# Match one char with * and keep going
simple_matcher(pattern[0:], string[1:])
or
# Don't use the *
simple_matcher(pattern[1:], string[0:])
or
# Only match one char with *
simple_matcher(pattern[1:], string[1:]))
Result = namedtuple('Result', ['pattern', 'string', 'expected'])
class TestSimpleMatcher(unittest.TestCase):
def test_empty_string(self):
results = [Result("", "", True),
Result("a", "", False),
Result("?", "", False),
Result("*", "", True),
Result("**", "", True),
Result("***", "", True)]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_empty_pattern(self):
results = [Result("", "", True),
Result("", "a", False),
Result("", "1", False),
Result("", "A", False),
Result("", "aaasdfasdf", False)]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_literals_against_one_char_string(self):
results = [
Result("a", "a", True),
Result("A", "A", True),
Result("1", "1", True),
Result("2", "a", False),
Result("4", "A", False),
Result("B", "1", False)
]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_question_marks_against_one_char_string(self):
results = [
Result("?", "a", True),
Result("?", "A", True),
Result("?", "1", True),
Result("??", "a", False),
Result("??", "A", False),
Result("??", "1", False),
]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_asteriks_against_one_char_string(self):
results = [
Result("*", "a", True),
Result("*", "A", True),
Result("*", "1", True),
Result("**", "a", True),
Result("***", "a", True),
Result("*****", "a", True),
]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_combinations_against_one_char_string(self):
results = [
Result("*?", "a", True),
Result("*A", "A", True),
Result("*?*", "a", True),
Result("*A*", "A", True),
Result("*?a", "a", False),
Result("*B", "A", False),
Result("*??*", "a", False),
Result("*A*?", "A", False),
]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
def test_combinations_against_three_char_string(self):
results = [
Result("*?", "aaa", True),
Result("???", "aaa", True),
Result("?*A", "BAA", True),
Result("*E*", "1EF", True),
Result("*", "123", True),
Result("****", "123", True),
Result("*?a*", "abc", False),
Result("*B", "Bod", False),
Result("????", "joe", False),
]
for pattern, string, expected in results:
self.assertEqual(simple_matcher(pattern, string), expected)
if __name__ == '__main__':
unittest.main()
