Dynamic ProgrammingStringRecursion
Implement matching for a tiny regular-expression language. In the pattern, . matches any single character, and * means 'zero or more of the character just before it' (that character can be a letter or .). The match must cover the entire input string. Decide whether the string matches the pattern.
Input
Line 1: the string s (it may be empty), lowercase letters. Line 2: the pattern p, made of lowercase letters, . and *. A * always follows a letter or a . and is never the first character.
Output
Print true if the pattern matches the whole string, otherwise false.
Constraints
0 <= length of s <= 20 1 <= length of p <= 30
Example 1
Input
aa a*
Output
true
a* matches any number of a's.
Example 2
Input
ab .*
Output
true
.* matches anything.
Example 3
Input
aab c*a*b
Output
true
c* matches zero c's, a* matches aa, then b.