Find a match for query within text

Asked by At

This question was asked recently during interview and i couldn't solve so need some suggestion how can i solve the problem

Declaration: I can not use REGEX or any in-built libraries

***** Problem Statement is as below*********

**matches Input: text (string), query (string) Output: true if you can find a match for query within text, false otherwise If there are no special characters, most languages have a contains method that will just do this. One special character: '?' -- if you find '?' in the query string, it signals that the previous character is optional (matches 0 or 1 times).

Examples:

  • No question marks:
  • matches("hello World", "hello") returns true
    • matches("hello World", "world") returns false
    • matches("hello World", "o W")returns true
    • matches("hello World", "W o") returns false
    • matches("hello World", "h W") returns false
    • With question marks -- "l?" means "optional l":
    • matches("heo World", "hel?o") returns true
    • matches("helo World", "hel?o") returns true matches("hello World", "hel?o") returns false
    • Make sure you understand this case:
    • matches("hello World", "hell?lo") returns true
    • You can have more than one question mark:
    • matches("hello World", "ex?llo Worlds?") returns true

***** My approach was as below*********

public class StringPatternMatch
{
    public static bool MatchPattern(string inputText, string pattern)
    {
        int count = 0; int patternIndex = 0;

        for (var i = 0; i < inputText.Length; i++)
        {
            if (patternIndex > pattern.Length)
                break;

            if (inputText[i] == pattern[patternIndex] ||
                (inputText[i] != pattern[patternIndex] && pattern[patternIndex + 1] == '?'))
                count++;

            patternIndex++;
        }

        return pattern.Length == count;
    }
}

traverse both strings from one side to other side (say from rightmost character to leftmost). If we find a matching character, we move ahead in both strings with increasing counter for pattern - at the end match count with pattern-length

Also i have provided my code but that doesn't cover all the cases

Of course i didn't go next round, but i am still thinking about this problem and haven't found accurate solution - hope to see some interesting answers!

1 Answers

2
maraca On Best Solutions

Your idea can work but your implementation is over-simplified:

// assumes the pattern is valid, e.g. no ??
public static boolean matches(String string, String pattern) {
    int p = 0; // position in pattern
    // because we only return boolean we can discard all optional characters at the beginning of the pattern
    while (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?')
        p += 2;
    if (p >= pattern.length())
        return true;
    for (int s = 0; s < string.length(); s++) // s is position in string
        // find a valid start position for the first mandatory character in pattern and check if it matches
        if (string.charAt(s) == pattern.charAt(p) && matches(string, pattern, s + 1, p + 1))
            return true;
    return false;
}

private static boolean matches(String string, String pattern, int s, int p) {
    if (p >= pattern.length()) // end of pattern reached
        return true;
    if (s >= string.length() || string.charAt(s) != pattern.charAt(p)) // end of string or no match
        // if the next character of the pattern is optional check if the rest matches
        return p + 1 < pattern.length() && pattern.charAt(p + 1) == '?' && matches(string, pattern, s, p + 2);
    // here we know the characters are matching
    if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?') // if it is an optional character
        // check if matching the optional character or skipping it leads to success
        return matches(string, pattern, s + 1, p + 2) || matches(string, pattern, s, p + 2);
    // the character wasn't optional (but matched as we know from above)
    return matches(string, pattern, s + 1, p + 1);
}