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.
|