A regular expression is a pattern describing how a particular string
should be formed. For the purposes of this problem, a regular expression consists
of atoms. Each atom is either a single lowercase letter (which matches
exactly one of that letter), or a single lowercase letter followed by an
asterisk ('*'), which matches zero or more of that letter. A string matches a
regular expression if it can be partitioned into substrings which match the
atoms of the regular expression in the same order. For example, the regular
expression ab*c*b is matched by the strings ab, abb,
acb and abbbcccb, but not by ba, accbb or
babcb.
You have a string text which ought to match the regular expression
regex. However, it may have been corrupted. Return the string S that
satisfies the following conditions.
- S has the same number of characters as text.
- S matches regex.
- The number of positions in which S differs from text is
minimal.
- S is lexicographically smallest amongst strings that satisfy the other
conditions.
If there is no string that satisfies the above conditions, return the empty
string. |