Connection Status:
Competition Arena > UnknownNames

UnknownNames

TC China 08 - Finals · 2008-11-23 · by boba5551

TC China 08 - Finals · 2008-11-23 · by boba5551 · Brute Force, Simple Search, Iteration, Sorting, String Manipulation
Class Name: UnknownNames
Return Type: String[]
Method Name: sortNames
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] questionMarkNames, where each element represents a single name, and all names have the same length. Some of the letters are missing, and those letters are represented by question marks ('?'). Arrange the names in a vertical row, such that corresponding characters in each name are in the same column. Then, order the names so that each column is sorted in non-decreasing order from top to bottom. You can replace each question mark with any letter to achieve this.

Return a String[] containing the lexicographically earliest ordering that you can achieve. If there is no way to achieve the goal, return an empty String[] instead. An ordering A comes before an ordering B if A contains an alphabetically earlier name at the first index where they differ.

Constraints

  • questionMarkNames will contain between 2 and 50 elements, inclusive.
  • Each element of questionMarkNames will containt between 1 and 50 characters, inclusive.
  • All elements of questionMarkNames will be of the same length.
  • Each character of each element of questionMarkNames will be an uppercase letter ('A'-'Z') or a question mark ('?').
Examples
0)
{"?ED?", "TO??", "????"}
Returns: {"AAAA", "AEDA", "TODA" }

If we make the order of names 0 1 2 then the lexicographically earliest ordering is AEDA TODA TODA 0 2 1 AEDA AEDA TOEA 1 0 2 TO?? TED? T??? - IMPOSSIBLE for this order, because O is after E, etc.

1)
{"T???????", "SO??????", "?MP?????", "??OC????", "???BO???", "????MD??", "?????CE?", "??????CR"}
Returns: {"AAAAAACR", "AAAAACER", "AAAAMDER", "AAABODER", "AAOCODER", "AMPCODER", "SOPCODER", "TOPCODER" }
2)
{"??", "??"}
Returns: {"AA", "AA" }
3)
{"IUH?JEUD", "?ERD??EW", "REWEHTQ?"}
Returns: { }
4)
{"IMP?", "OSS?", "IBL?", "EAW?"}
Returns: { }

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

Coding Area

Language: C++17 · define a public class UnknownNames with a public method vector<string> sortNames(vector<string> names) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous