Class name: Regex
Method name: match
Parameters: String[], String
Returns: String[]
Regular expressions are often used as patterns for matching text. A regular
expression is a string that describes a regular language. It can be used to
match any string that is in this regular language.
The language that a regular expression can be written in is a very simple one.
For this problem we will use a special, stripped down type of regular
expression.
The syntax for this form of regular expression is quite simple. Any character
that is not a parenthesis ('(' or ')'), not an asterisk ('*'), and not a period
('.') matches itself. That is, the pattern 'abc' matches the string 'abc' (and
only that string). The period is a special character that matches a single
occurrence of any character. Thus, the pattern '.' matches all
single-character strings.
An asterisk immediately following any character causes that character (or a
group of characters, if the previous character is a close parenthesis - see
below) to be matched zero or more times. Thus, the pattern 'a*' matches the
empty string, as well as the strings 'a', 'aa', 'aaa', etc and '.*' matches the
empty string, 'ab', 'ahdj', etc. It is a syntax error for an asterisk to occur
at the beginning of the pattern or immediately following another asterisk.
The parentheses can be used for grouping. All parentheses must balance
perfectly, and all enclosed subexpressions must contain at least one character.
An asterisk immediately following a closing parenthesis indicates that the
enclosed subexpression may be matched zero or more times. Thus, the pattern
'a(bc*d)*e' matches the strings 'ae', 'abde', 'abcde', 'abcccde',
'abdbccdbcccdbdbde', etc. It is a syntax error for an asterisk to immediately
follow an opening parenthesis.
Implement a class Regex, which contains a method match. match takes a list of
strings and a regular expression, and return a new list, containing only those
given strings that match the given regular expression pattern.
The method signature is:
public String[] match(String[] text, String pattern);
The list of strings will be provided in a String[]. The pattern will be a
regular expression, as defined above.
Constraints:
- Each element in the String[] will only contain letters, digits, and spaces
- The length of the String[] will be at most 50 Strings
- The length of each element in the String[] will be at most 50 characters
- The length of the pattern will be at most 50 characters
- The pattern will be syntactically correct, according to the rules described
above
- Aside from the special characters ('*', '.', '(', and ')'), all characters in
the pattern must be letters, digits, or spaces
The tester will ensure that all of the above constraints are met before any
input is passed to your method.
Notes:
- For a string to match the pattern, it must match the pattern in its entirety.
That is, the pattern 'ab' does NOT match the string 'xabx'.
- The matching is case-sensitive (an 'a' in a regular expression never matches
an 'A').
- The order in which the matching strings are placed in the returned ArrayList
does not matter
- If no Strings match the pattern, an empty instance of ArrayList is returned.
Example:
Consider the following ArrayList of Strings:
["e", "abcde", "ae", "abdade", "abcccbcbbbcccbcbdade", "a"]
If the pattern is '(a(bc*)*d)*e', then:
- "e" DOES match the pattern
- "abcde" DOES match the pattern
- "ae" does NOT match the pattern (a 'd' must follow the 'a' before the 'e')
- "abdade" DOES match the pattern
- "abcccbcbbbcccbcbdade" DOES match the pattern
- "a" does NOT match the pattern (the string must end with an 'e')
Thus, the method should return the following ArrayList:
["e", "abcde", "abdade", "abcccbcbbbcccbcbdade"]
|