Statistics

Problem Statement for "PatternOptimizer"

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

  1. "*??*a"

    Returns: "*??a"

  2. "*b**a*"

    Returns: "*b*a*"

  3. "cla??"

    Returns: "cla??"

  4. "*?*?*?*"

    Returns: "*???"

  5. "T***nd?*"

    Returns: "T*nd*?"

  6. "????*???*caa??aaa*a*babc**?*b*?"

    Returns: "*???????caa??aaa*a*babc*?b*?"

  7. "a"

    Returns: "a"

  8. "?*c"

    Returns: "*?c"

  9. "aa*a?*aa*a*a?b?*a*?*caaa"

    Returns: "aa*a*?aa*a*a?b*?a*?caaa"

  10. "*ac??a**b***c"

    Returns: "*ac??a*b*c"

  11. "a*?c**a*bc?a?a*c?a?ab"

    Returns: "a*?c*a*bc?a?a*c?a?ab"

  12. "?c?*aac*a????aa??*?*a**?b*ca*a*ca***c?**a?cca"

    Returns: "?c*?aac*a????aa*???a*?b*ca*a*ca*c*?a?cca"

  13. "?"

    Returns: "?"

  14. "*"

    Returns: "*"

  15. "*baa?*a?b????a*a?*?"

    Returns: "*baa*?a?b????a*a*??"

  16. "*b?a?*?*???**c*c??*a?a?*??**aa?*?a*c??a??a"

    Returns: "*b?a*?????c*c*??a?a*???aa*??a*c??a??a"

  17. "?ba**?b??a?c??aa*a*"

    Returns: "?ba*?b??a?c??aa*a*"

  18. "a*?****?a*??a?a????a**?aa*?*a**??aa***??"

    Returns: "a*??a*??a?a????a*?aa*?a*??aa*??"

  19. "a*?*???b?*??a?a*?*?c?aa*???*?a?*?aa"

    Returns: "a*????b*???a?a*??c?aa*????a*??aa"

  20. "a*?aaaa*aa?a*a*c**?*a??*?*a?*???b**a*a*?***?*?*a?"

    Returns: "a*?aaaa*aa?a*a*c*?a*???a*????b*a*a*???a?"

  21. "**a**??*a**???**??*"

    Returns: "*a*??a*?????"

  22. "*???a***a?a"

    Returns: "*???a*a?a"

  23. "c?*?a**?b?*a*?*a??*aaa**??a**a?a"

    Returns: "c*??a*?b*?a*?a*??aaa*??a*a?a"

  24. "ac?c*?*a*??**a?*?*???a"

    Returns: "ac?c*?a*??a*?????a"

  25. "a?**?b***?*?**b****?b?*****a??**??**"

    Returns: "a*??b*??b*?b*?a*????"

  26. "a**a*?*****?*?*??*??**?***?a*?***a***?**?a*????*?"

    Returns: "a*a*?????????a*?a*??a*?????"

  27. "???**??**?"

    Returns: "*??????"

  28. "**?a***?**???**?**?*******?a"

    Returns: "*?a*???????a"

  29. "??**?*a?*??***??a??*???"

    Returns: "*???a*?????a*?????"

  30. "*??*???*???**?*?*?*?**?*****?aaa?***a**?*?*??"

    Returns: "*??????????????aaa*?a*????"

  31. "*?*a*a?a?**????a**??*??*???aa??*?**"

    Returns: "*?a*a?a*?????a*???????aa*???"

  32. "a?a???*?????**aa?*a?*??**a???"

    Returns: "a?a*????????aa*?a*???a???"

  33. "a*??*a?*?*"

    Returns: "a*??a*??"

  34. "*?a?*****?*a??*?*??*?"

    Returns: "*?a*??a*??????"

  35. "***a?**a????aa**?????a*?****?a???*a**????****?****"

    Returns: "*a*?a????aa*?????a*??a*???a*?????"

  36. "*b*x*k?q*?*dkkbuuj?sjoa*aa*oro*?o*c?d*?waaw?t?y?ie"

    Returns: "*b*x*k?q*?dkkbuuj?sjoa*aa*oro*?o*c?d*?waaw?t?y?ie"

  37. "*aekldaun**eyz**???ighg?*oipmna*b?yeue**tas*e?iksd"

    Returns: "*aekldaun*eyz*???ighg*?oipmna*b?yeue*tas*e?iksd"

  38. "ycujo**fe*s*apfza?jaa*yca?oy*?yeqp?nwuuqocbssq*ges"

    Returns: "ycujo*fe*s*apfza?jaa*yca?oy*?yeqp?nwuuqocbssq*ges"

  39. "?eyagg*wkade*a?hccbcambeaa?wc*?dyye?*k?icnc**?qhia"

    Returns: "?eyagg*wkade*a?hccbcambeaa?wc*?dyye*?k?icnc*?qhia"

  40. "khv?a*q*squwaqzdq?dgu*ohqa*li?es?kqstyqedatk??akwa"

    Returns: "khv?a*q*squwaqzdq?dgu*ohqa*li?es?kqstyqedatk??akwa"

  41. "efv?tqq**w*oasessac?hhli?yp?dasstioy*c*xr??tacsca?"

    Returns: "efv?tqq*w*oasessac?hhli?yp?dasstioy*c*xr??tacsca?"

  42. "x*kyfo??uuzriw*va*?*gzq?axy**??*ucnwuen?y*lw*ii?cy"

    Returns: "x*kyfo??uuzriw*va*?gzq?axy*??ucnwuen?y*lw*ii?cy"

  43. "a*t??z?mi?*zr*szijfe?u?igbmaynb*ko?a*zue?wnkw?pq*?"

    Returns: "a*t??z?mi*?zr*szijfe?u?igbmaynb*ko?a*zue?wnkw?pq*?"

  44. "fk*iquk??*ofkhp*?uv?csacgfw?ax?b?ayzuqtym*faw*?sti"

    Returns: "fk*iquk*??ofkhp*?uv?csacgfw?ax?b?ayzuqtym*faw*?sti"

  45. "gmn***ufcam*pm?*?a?cs?om*ix?iuizauv??amg?jas*?i*wy"

    Returns: "gmn*ufcam*pm*??a?cs?om*ix?iuizauv??amg?jas*?i*wy"

  46. "icwyj?*??kvci?eqj?i?wzs??ag*q**?*aipj*?a*e*v*m*oga"

    Returns: "icwyj*???kvci?eqj?i?wzs??ag*q*?aipj*?a*e*v*m*oga"

  47. "*??wowch*budeun?x?aa*e*ceu?sq?qztucaiegcq*myrwjrqm"

    Returns: "*??wowch*budeun?x?aa*e*ceu?sq?qztucaiegcq*myrwjrqm"

  48. "suysq*kuuhyumei??c*yytqma?w*gck***?*u?*xeys**a?*z*"

    Returns: "suysq*kuuhyumei??c*yytqma?w*gck*?u*?xeys*a*?z*"

  49. "??cesxq?*b?*ily*?*xlk**?oenirgsat*??xqcktw*?gqmxec"

    Returns: "??cesxq*?b*?ily*?xlk*?oenirgsat*??xqcktw*?gqmxec"

  50. "*axa?xmmy?zcatwmyzv?tam???akc??eel*cws?lyy?*onar?n"

    Returns: "*axa?xmmy?zcatwmyzv?tam???akc??eel*cws?lyy*?onar?n"

  51. "c?uckxe*aqmb*?**geykc*ouwiccwo?smu?uama*?scytjuqtj"

    Returns: "c?uckxe*aqmb*?geykc*ouwiccwo?smu?uama*?scytjuqtj"

  52. "??ofe**yf*?uo*qg?aqagze?oswud*ra*kmic?mmpgwomo*wla"

    Returns: "??ofe*yf*?uo*qg?aqagze?oswud*ra*kmic?mmpgwomo*wla"

  53. "wk*vh?eu?*?mana?yqpauaa*y*rpt?ax?suz?*a?x?twnuwie?"

    Returns: "wk*vh?eu*??mana?yqpauaa*y*rpt?ax?suz*?a?x?twnuwie?"

  54. "ucjayghnq??gyy?uvii?lpa*y?*eua*n??*cnynmdiioqy*bik"

    Returns: "ucjayghnq??gyy?uvii?lpa*y*?eua*n*??cnynmdiioqy*bik"

  55. "gpc*k**?k?aeue*cc*a*psoaojst*s?wi?l?k?cwi?**ms?a*z"

    Returns: "gpc*k*?k?aeue*cc*a*psoaojst*s?wi?l?k?cwi*?ms?a*z"

  56. "???xx?*xx?x?*xxx???**?x??*?*?*?xx***??**??**??x??*"

    Returns: "???xx*?xx?x*?xxx*????x*?????xx*??????x*??"

  57. "****?x?***??xx*x?**?*??xx?x?x??z*z*??*x?*x?*?**z?*"

    Returns: "*?x*???xx*x*????xx?x?x??z*z*??x*?x*??z*?"

  58. "x?????z?xx?x**xx?*xyy*?*????xx*???**x???????*?y**?"

    Returns: "x?????z?xx?x*xx*?xyy*?????xx*???x*????????y*?"

  59. "***xy?x*?yxx**?x****?x*?*?x***x?*??x**?xz??*??*?*x"

    Returns: "*xy?x*?yxx*?x*?x*??x*x*???x*?xz*?????x"

  60. "x?*?x*?x?**??xxy*?x?x?x?????x*?xxx??xz?*y*?*?*x*?*"

    Returns: "x*??x*?x*???xxy*?x?x?x?????x*?xxx??xz*?y*??x*?"

  61. "???**???***?*?***??*??*?***???**???***????????*??*"

    Returns: "*?????????????????????????????"

  62. "?*?**??***??***???**???*?*??*?**??*????*?*???*????"

    Returns: "*??????????????????????????????"

  63. "????????*?*?*??*?****?***?***???**??***??**?*?????"

    Returns: "*????????????????????????????"

  64. "??**???*?****?*????***?*????**??***????????****?**"

    Returns: "*???????????????????????????"

  65. "??*?????***???**?????***???***??*??**??***?***????"

    Returns: "*?????????????????????????????"

  66. "***??*????*????**??*???*?????*?*??*?****?**?*?????"

    Returns: "*???????????????????????????????"

  67. "*?****?**??*??*?*?*???*?**??**?**??*?*?*****???**?"

    Returns: "*???????????????????????"

  68. "????*?**???*?*?*??????**???****?????*????****?*?*?"

    Returns: "*???????????????????????????????"

  69. "*????*???*?*???**???**?*?***???*?*????*??*??******"

    Returns: "*????????????????????????????"

  70. "?*?*?*???***?*??**?***??????????*??*?????*?*?***?*"

    Returns: "*??????????????????????????????"

  71. "?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*"

    Returns: "*?????????????????????????"

  72. "*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?"

    Returns: "*?????????????????????????"

  73. "?*?*?*?*?*?*?*?*?*?*?*?*z*?*?*?*?*?*?*?*?*?*?*?*?*"

    Returns: "*????????????z*????????????"

  74. "*?*?*?*?*?*?*?*?*?*?*?*?z?*?*?*?*?*?*?*?*?*?*?*?*?"

    Returns: "*????????????z*?????????????"

  75. "**************************************************"

    Returns: "*"

  76. "??????????????????????????????????????????????????"

    Returns: "??????????????????????????????????????????????????"

  77. "?*************************************************"

    Returns: "*?"

  78. "?????????????????????????????????????????????????*"

    Returns: "*?????????????????????????????????????????????????"

  79. "T*??*?"

    Returns: "T*???"

  80. "T***nd?*"

    Returns: "T*nd*?"

  81. "cla?*"

    Returns: "cla*?"

  82. "??*"

    Returns: "*??"

  83. "**"

    Returns: "*"

  84. "?*"

    Returns: "*?"

  85. "??****?ab?**?c**??ad*"

    Returns: "*???ab*??c*??ad*"

  86. "????****"

    Returns: "*????"

  87. "A?*"

    Returns: "A*?"

  88. "x"

    Returns: "x"

  89. "T***nd?*nd?*"

    Returns: "T*nd*?nd*?"

  90. "*?"

    Returns: "*?"

  91. "**asg*??*?*?*?*?g**h????*?*?*p*?"

    Returns: "*asg*??????g*h*??????p*?"

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.
This problem was used for: