TopCoder problem "PatternOptimizer" used in SRM 269 (Division I Level One , Division II Level Two)



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.

 

Definition

    
Class:PatternOptimizer
Method:optimize
Parameters:String
Returns:String
Method signature:String optimize(String pattern)
(be sure your method is public)
    
 

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*?"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4717

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8002&pm=4717

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

String Manipulation