ClosestRegex | Topcoder Archive

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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.