Connection Status:
Competition Arena > ClosestRegex

ClosestRegex

SRM 410 · 2008-07-19 · by bmerry

SRM 410 · 2008-07-19 · by bmerry · Dynamic Programming, String Manipulation
Class Name: ClosestRegex
Return Type: String
Method Name: closestString
Arg Types: (string, string)
Problem Statement

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.

  1. S has the same number of characters as text.
  2. S matches regex.
  3. The number of positions in which S differs from text is minimal.
  4. 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.

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
0)
"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'.

1)
"topcoder"
"t*px*coa*de*"
Returns: "ttpcodee"

Changing the string to ttpcodee requires two changes.

2)
"cmu"
"c*m*fm*u*"
Returns: "cfu"

Any of fmu, cfu and cmf would require one change, but cfu is first lexicographically.

3)
"aaaaacccc"
"a*abc*"
Returns: "aaaaabccc"
4)
"short"
"lo*ts*of*let*ter*s"
Returns: ""

No 5-letter string matches the regex.

Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ClosestRegex with a public method string closestString(string text, string regex) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous