Connection Status:
Competition Arena > PatternOptimizer

PatternOptimizer

SRM 269 · 2005-10-26 · by Andrew_Lazarev

SRM 269 · 2005-10-26 · by Andrew_Lazarev · String Manipulation
Class Name: PatternOptimizer
Return Type: String
Method Name: optimize
Arg Types: (string)
Problem Statement

Problem Statement

Some dictionaries use a word pattern that consists of letters, '?' symbols which each denote exactly one letter, and '*' symbols which each denote zero or more letters.

Interestingly, some patterns represent the same set of words. For example, "*??*a" and "?*?a" (quotes for clarity only) patterns both represent all words that consist of three or more letters and end with 'a'.

You will be given a String pattern. Your method should return the shortest pattern that represents the same set of words as the given pattern. Return the lexicographically first in case of tie.

Notes

  • Note that '*' comes before '?' in the lexicographical order.

Constraints

  • pattern will contain between 1 and 50 characters, inclusive.
  • pattern will contain only letters ('a'-'z', 'A'-'Z'), '?' and '*'.
Examples
0)
"*??*a"
Returns: "*??a"
1)
"*b**a*"
Returns: "*b*a*"
2)
"cla??"
Returns: "cla??"
3)
"*?*?*?*"
Returns: "*???"
4)
"T***nd?*"
Returns: "T*nd*?"

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

Coding Area

Language: C++17 · define a public class PatternOptimizer with a public method string optimize(string pattern) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous