FastPrep
Problem · Dynamic Programming

Is Regex Matching

Learn this problem
● HardAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

The developers at Amazon are developing a regex matching library for their NLP use cases. A prototype regex matching has the following requirements:

  • The regex expression contains lowercase English letters, '(', ')', '.', and '*'.
  • '.' matches with exactly one lowercase English letter.
  • A regular expression followed by '*' matches with zero or more occurrences of the regular expression.
  • If an expression is enclosed in parentheses '(' and ')', it is treated as one expression and any asterisk '*' applies to the whole expression. It is guaranteed that no expression enclosed within parenthesis contains any '*' but is always followed by '*'. Also, there is no nested brackets sequence in the given regex expression for the prototype.

    • For example,

    Regex "(ab)*d" matches with the strings "d", "ababd", "abd", but not with the strings "abbd", "abab".
  • Regex "ab*d" matches with the strings "abbbd", "ad", "abd", but not with strings "ababd".
  • Regex "a(b.d)*" matches with the strings "abcdbcd", "abcdbed", "abed", "a" but not with strings "bcd", "abd".
  • Regex "(.)*" matches with the strings "a", "aa", "aaa", "b", "bb" and many more but not "ac", "and", or "bcd" for example.

    • Given an array, arr, of length k containing strings consisting of lowercase English letters only and a string regex of length n, for each of them find whether the given regex matches with the string or not and report an array of strings "YES" or "NO" respectively.

    Function

    isRegexMatching(regex: String, arr: String[]) → String[]

    Complete the function isRegexMatching in the editor.

    isRegexMatching has the following parameters:

    • regex: A regex
    • arr[k]: An array of strings

    Returns

    string[]: An array of strings of size k where the ith string is "YES" if the ith string in arr matches with regex, otherwise it is "NO".

    🌷༊·°Credit to Alex𓂃🖊

    Examples

    Example 1

    regex = "ab(e.r)*e"arr = ["abbeere", "abefretre"]return = ["NO", "YES"]
    Here, n = 9, regex = "ab(e.r)*e", k = 2, arr = ["abbeere", "abefretre"]
  • arr[0] = "abbeere" doesn't match the regex "ab(e.r)*e".
  • arr[1] = "abefretre" matches the regex "ab(e.r)*e", if we replace '*' with 2 occurrences of "e.r", i.e. it becomes "abe.re.re". Now, replace both '.' with 'f' and 't' respectively.
    • Hence, the answer is ["NO", "YES"].

    Example 2

    regex = "..()*e*"arr = ["code", "abeee", "cd"]return = ["NO", "YES", "YES"]
    Here, n = 8, regex = "..()*ex", k = 3, arr = ["code", "abeeee", "cd"]
  • arr[0] = "code" doesn't matches the regex "..()*ex".
  • arr[1] = "abeeee" matches the regex "..()*ex", if we replace first '*' with 0 occurrences of "" (an empty string) and second '*' with 3 occurrences of "e", i.e. it becomes "..eee". Now, replace both '.' with 'a' and 'b' respectively.
  • arr[2] = "cd" matches the regex "..()*ex", if we replace first '*' with 0 occurrences of "" and second '*' with 0 occurrences of "e", i.e. it becomes "..". Now, replace both '.' with 'c' and 'd' respectively.
    • Hence, the answer is ["NO", "YES", "YES"].

    More Amazon problems

    drafts saved locally
    public String[] isRegexMatching(String regex, String[] arr) {
  // write your code here
}
    regex"ab(e.r)*e"
    arr["abbeere", "abefretre"]
    expected["NO", "YES"]
    checking account