Problem Statement
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.
Definition
- Class:
- ClosestRegex
- Method:
- closestString
- Parameters:
- String, String
- Returns:
- String
- Method signature:
- String closestString(String text, String regex)
- (be sure your method is public)
Constraints
- text will contain between 1 and 50 characters, inclusive.
- text will contain only lowercase letters ('a' - 'z').
- regex will contain between 1 and 50 characters, inclusive.
- regex will contain only lowercase letters and '*'s.
- The first character of regex will not be a '*'.
- regex will not contain two consecutive '*'s.
Examples
"abcd"
"bcdd"
Returns: "bcdd"
Here there are no asterisks, so only one string can match. 'a' must be changed to 'b', 'b' to 'c' and 'c' to 'd'.
"topcoder"
"t*px*coa*de*"
Returns: "ttpcodee"
Changing the string to ttpcodee requires two changes.
"cmu"
"c*m*fm*u*"
Returns: "cfu"
Any of fmu, cfu and cmf would require one change, but cfu is first lexicographically.
"aaaaacccc"
"a*abc*"
Returns: "aaaaabccc"
"short"
"lo*ts*of*let*ter*s"
Returns: ""
No 5-letter string matches the regex.
"abc"
"def"
Returns: "def"
"abc"
"ab"
Returns: ""
"abc"
"ab*cd"
Returns: "acd"
"cbc"
"a*b*"
Returns: "abb"
"acde"
"a*bcde*"
Returns: "bcde"
"z"
"a*"
Returns: "a"
"a"
"z*"
Returns: "z"
"p"
"p*"
Returns: "p"
"x"
"x"
Returns: "x"
"x"
"y"
Returns: "y"
"ababababababababababababababababababababababababab"
"a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*"
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababab"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*b*a*"
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"ababababababababababababababababababababababababab"
"a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*"
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"bcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxa"
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
Returns: "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
"cb"
"c*ca*"
Returns: "ca"
"qq"
"o*ot*a*a*p*a*n*"
Returns: "oa"
"bbbcaabcbc"
"c*cba*a"
Returns: "cbaaaaaaaa"
"cbdaaeed"
"e*e*ec*ee*"
Returns: "ecccceee"
"deeia"
"g*gf*ha*f*"
Returns: "gffha"
"bdadddca"
"b*bc*a*d*adc*c"
Returns: "baadadcc"
"ggooglegooglegooglegoogleoogle"
"o*df*l*o*df*l*p*o*df*l*o*df*l*podfl*p*p*p"
Returns: "oooodllloodllloodllloodlpodflp"
"adadfbbasdfasdbfadfasdfqadfadfbadsfbadfadfd"
"a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*r*s*t*u*v*"
Returns: "aaaaabbbbdddddddddddddddddddddddddddddddddd"
"shortestotnakraj"
"lo*ts*of*let*ter*s*ealsr*asra*a*"
Returns: "ltoleteealsasraa"
"abfjdsjdhfsjfksdkjfywekjdssgkjkjjksjk"
"j*h*f*z*d*g*d*d*d*s*f*fsg*f*fg*s*s*d*a*z*a*h*z*t*e"
Returns: "jjjjjjjhhfsfffsffffffffffssssssssssae"