002 Regular Expressions

Your challenge is to write your own miniature regular expression matcher. The matcher should handle regular expressions of the form a, where a can be any letter, and a* where a* means zero or more repetions of the same letter.

For example, given a regular expression x*yz, it should match the strings xxyz, xyz, yz, but not yyz.

• The solution should be a function match that, given a regular expression and a string, returns true if the string was a match, and false otherwise.
• Note that * should be non-greedy, e.g. make sure that x*x matches the string xx.
• Assume that the regular expression should match the complete input string, e.g. a should not match ab.
• For the sake of simplicity, you can assume we will only work with the lower-case part of the ASCII alphabet, i.e the letters a-z.

Examples:

match("a", "a") -> true
match("b", "bb") -> false
match("a*a", "a") -> true
match("b*c", "bbbbc") -> true
match("xy*x", "xx") -> true
match("z*z", "zz") -> true
match("m*n", "mmmnm") -> false