2

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.

closed as too broad by user40980, Ixrec, user22815, gnat, GlenH7 Feb 13 '16 at 23:41

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    Was that an interview question while applying to a compiler development position? – Patrick Aug 1 '13 at 9:19
  • 1
    It is an interesting comment on the state of education in this field that, out of the first five answers posted, NOBODY mentioned the Boyer-Moore string search algorithm. – John R. Strohm Aug 1 '13 at 15:05
  • 2
    its an interesting comment on the state of education that someone is surprised that people who work in their field haven't memorized a bunch of trivia. – Jonathan Henson Aug 1 '13 at 17:42
5

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)

  • I don't think what you describe for * works if the first character after the * is also in the * part of the pattern – jk. Aug 1 '13 at 6:47
  • @jk Good point, revising. – Jonathan Henson Aug 1 '13 at 6:48
  • @JonathanHenson Having "" in the pattern string means it is no longer deterministic. Even if you find the next character in the pattern (and assuming it isn't a ? or another *) following the * in the matching string, it may very well be ignored by the *. Example, aba could match abba or aba, and without taking into consideration both possibilities, you accept either abba or aba in that case. – Neil Aug 1 '13 at 8:21
  • @Neil, you are correct, but I am taking the greedy approach so that is how I would expect it to behave. – Jonathan Henson Aug 1 '13 at 15:04
3

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 would actually give this answer, but I would be expecting the interviewer to say something like, "Well I am glad you actually have some real world experience, and that is how you would do it in production code, but now it is time to solve the damn problem." – Jonathan Henson Aug 1 '13 at 7:00
  • yep even this solution though gives rise to a potential discussion of what the requirements are. e.g. does alphanum char include _ like Euphoric's answer? what about non ascii chars which my solution wont match. – jk. Aug 1 '13 at 8:02
  • 1
    @JonathanHenson On the contrary, if I were the interviewer, I would be worried if the programmer offering the solution didn't propose this possibility, and even more so worried if the programmer actually was familiar with regular expressions. Sometimes the best program a programmer can write is one that uses the best library a programmer can use. – Neil Aug 1 '13 at 8:06
  • sort of relevant blogs.msdn.com/b/ericlippert/archive/2011/02/14/… particularly the last bit – jk. Aug 1 '13 at 9:56
  • 1
    @KChaloux No I mean "was". A programmer which is familiar with a library efficiently designed to take care of his particular problem without disadvantages, and the programmer doesn't take advantage of that library, is worrisome to me. – Neil Aug 2 '13 at 7:53
2

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

1

Pragmatic approach:

  1. Convert pattern string into a valid Regex string.
    • Simply replace ? with \w and * with \w* or \w+
  2. Use the regex to search the pattern
  • If I were the interviewer, I would give your props for being a smart ass. Then I would tell you that you couldn't use a regex engine. Of course, I don't know what the purpose of the interview question is, so maybe that would be a suitable answer. – Jonathan Henson Aug 1 '13 at 6:58
  • technically \w matches more than alphanumumeric characters but yes something like this is what i'd do – jk. Aug 1 '13 at 6:58
  • 2
    @JonathanHenson Thats why I said pragmatic approach. Interviewers don't care about pragmatism. – Euphoric Aug 1 '13 at 6:59
  • @Euphoric agreed. Sometimes they do though, and that is the point. I know that your answer would impress me--though I would still make you solve the problem without regex. It is attractive to see people who ask for ways to simplify a problem. – Jonathan Henson Aug 1 '13 at 7:01
  • 1
    @JanHudec Not really. for example Java and .NET doesn't have one. I believe the reason is because regexes are much more powerful, so there is no reason to implement simple wildcard matching. – Euphoric Aug 6 '13 at 8:13
0

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!

0

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.