TopCoder problem "UnknownNames" used in TC China 08 - Finals (Division I Level Two)



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.

 

Definition

    
Class:UnknownNames
Method:sortNames
Parameters:String[]
Returns:String[]
Method signature:String[] sortNames(String[] names)
(be sure your method is public)
    
 

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)
    
{ "?E", "L?", "??", "L?"}
Returns: {"AA", "AE", "LE", "LE" }
3)
    
{"A???J?", "BC????", "?DE???", "??FG??", "???HI?"}
Returns: { }
4)
    
{"AAH????AB?EE??GCB?HE?G?CACA?A?B??A?JG?AGD????F?EEE",
 "?D?NI??JK?H?N?K???HKM?L?GE?N??G?K?L??M?HM??CP?E?NJ",
 "?KOVL?????K??TKP???L??N?N??O????MI?Y?QK?NR?E?RF???",
 "?M?Z??N?T??R????????TP?OQ??SY??Z?O?Z?YTL?RMG???YV?",
 "W???????Z?TX?Z???XZMYRNX??L??Q?????????L?T?J????Z?",
 "ZYZZ?????S?ZZZ?Z??ZV?Y????LZ?R?ZZVZZ?Z??ZT?M?V?Z??",
 "?Y?Z?Z?X??UZ?ZZ??ZZY?ZV?Z?MZ?W?Z??Z?ZZ?????TZ??Z?Z",
 "Z?????Z??ZV????Z????Z?????S????ZZZZ????Z???TZ?W?ZZ",
 "ZZ??ZZZ???WZZZ????Z?Z?Z?Z???Z?Z?ZZ?Z??Z??Z?W???ZZ?",
 "??????????Z?Z?Z??Z?ZZZ?Z??ZZ?Z?????ZZ??ZZZZZ??ZZ??",
 "?Z?Z???Z????Z?ZZ??Z?ZZZ?Z???Z?ZZ??Z?Z??Z??Z??Z???Z",
 "?Z?ZZ?Z??ZZ?ZZ???????Z???ZZZ?Z?ZZ?Z?ZZ?Z?ZZZ?Z??ZZ",
 "??Z??ZZ?Z?ZZ?ZZ????Z???Z??Z???????Z??Z??Z???Z?ZZ?Z",
 "ZZ??Z?ZZ??ZZZ??Z????ZZ?Z?ZZ??ZZ???Z?ZZ??ZZZZZZZ??Z",
 "?Z????ZZZ???Z??Z?Z?Z?Z????Z??ZZZZ??ZZ?Z?????Z??Z??",
 "Z???ZZZ??Z?ZZ??Z??Z?Z???Z???ZZ??Z???Z?ZZ??ZZ??Z??Z",
 "??????ZZ???Z?Z?ZZ?ZZ????Z??Z??????ZZ?ZZ?Z?Z?Z??Z??",
 "ZZZ?Z??ZZ???Z??Z?Z?ZZ?Z??ZZ?Z????ZZZ??Z??Z?ZZ??ZZZ",
 "Z?Z???ZZZ???ZZ?Z??Z???ZZZZZ??Z??Z??Z?Z?ZZZ?ZZ??Z?Z",
 "Z???Z???ZZ?Z??Z??ZZ??ZZZ??Z??ZZ?Z?????????Z???Z?ZZ",
 "Z?Z????Z?ZZZ?????Z???Z?Z??ZZ??Z??ZZZ??ZZZ?Z?ZZ?Z?Z",
 "???Z?????????ZZZZ??Z?Z??Z????Z??ZZ???Z?ZZ??????Z??",
 "???Z?Z?ZZZ?Z??Z?????Z??????ZZZ?Z?Z?ZZ?ZZZZZ?ZZZZ??",
 "Z??ZZ??Z?????Z????ZZZ?Z?Z??Z?ZZZ?Z?Z???Z?Z??????Z?",
 "ZZ?Z?ZZ?Z???ZZ????Z???Z?Z??Z?ZZZZ??ZZZ???ZZ?Z?ZZZ?",
 "??ZZ????ZZ??Z?Z????ZZZ?Z?Z?Z?ZZZ?Z???ZZ?ZZ???Z???Z",
 "Z??Z???Z?ZZZ???Z?Z?????Z???ZZ???Z?ZZZ?????Z??ZZZ??",
 "?Z????ZZZ??Z???????Z???Z???Z?Z?Z??Z?ZZ?ZZ?ZZZZ???Z",
 "?ZZZ?ZZZZ?ZZ?Z?ZZZZ?ZZ?Z?Z??Z?ZZ??ZZ?Z???Z??????ZZ",
 "ZZ?ZZZ??Z????Z?ZZZZZ?Z???Z??ZZ?Z???ZZ?Z?Z?ZZ??ZZZZ",
 "?ZZ?Z?ZZ?ZZZ?ZZ??ZZZZ?ZZ?Z?Z?????ZZ???ZZZZ?Z?Z?ZZ?",
 "Z??ZZ??ZZ???Z?ZZZ??Z??ZZ?Z?Z??????Z?ZZ?ZZZZ?Z?Z??Z",
 "???ZZ???ZZZZZZ???????ZZZZZ?Z?Z?ZZZZZ??ZZZ??ZZZ????",
 "Z?ZZ?Z?ZZ???ZZZZZ???ZZ?ZZ?Z??ZZ?Z????Z??Z?????ZZ?Z",
 "??Z?ZZZ?Z???Z???Z?ZZ???Z??ZZ???Z??ZZ??Z???Z?????ZZ",
 "?Z?Z?Z?Z?Z?Z?ZZ???Z??ZZ?ZZZ?Z???????Z?ZZ?ZZ???????",
 "Z??Z??Z???ZZZZZZ??ZZ???????ZZZZ?Z?????ZZ?Z??Z??ZZ?",
 "????????Z??ZZ????ZZ??Z?ZZ???Z?ZZ??Z?Z??ZZZ?ZZZ?ZZ?",
 "??Z??ZZ?Z?Z?????Z??Z?ZZZ??Z?Z?ZZ??ZZ?Z?Z?ZZ???ZZ??",
 "??ZZ???ZZ????????ZZZZ????Z??ZZ?Z?Z?ZZZZZZZ????ZZ??",
 "?ZZ?Z????ZZ???ZZZ?Z???Z?ZZZ???Z?ZZZ?????ZZZZZ?Z?ZZ",
 "????Z?Z??Z????Z??ZZZZZ??Z??ZZZ?ZZ??Z???Z?Z?Z???ZZ?",
 "Z???????Z?ZZZZ??Z?ZZZ?ZZZ??Z??Z??Z?Z?ZZZ?Z?Z?ZZ?ZZ",
 "?Z?ZZ??ZZZZ???ZZZZZZZ?ZZ????Z?Z?ZZ???Z?Z?ZZ???Z??Z",
 "??Z?Z??Z?Z??ZZ??Z?ZZ?Z???ZZ??ZZ???Z?????Z?Z?ZZ?Z?Z",
 "Z?Z??ZZ???ZZ?ZZZ?ZZZ??Z????ZZ???ZZ?ZZ????ZZ???ZZZ?",
 "????ZZ?ZZ?ZZ?ZZ??ZZZ???ZZZ??Z???Z??ZZ?Z?????Z????Z",
 "??ZZ?Z??Z?ZZ???ZZ?Z?Z?Z?????Z?Z???Z??ZZ??Z?Z?ZZ??Z", 
 "?ZZZZ??Z?Z?ZZZ?Z?Z?Z?ZZZ???Z??Z?ZZ??Z?Z??Z??Z?Z??Z",
 "ZZ?Z???Z??ZZZ?ZZZ?ZZ?ZZ?ZZ???ZZZZ?Z??Z?Z?Z?Z??Z??Z"}
Returns: 
{"AAHAAAAABAEEAAGCBAHEAGACACAAAABAAAAJGAAGDAAAAFAEEE",
"ADHNIAAJKAHENAKCBAHKMGLCGEANAAGAKALJGMAHMAACPFEENJ",
"AKOVLAAJKAKENTKPBAHLMGNCNEAOAAGAMILYGQKHNRAEPRFENJ",
"AMOZLANJTAKRNTKPBAHLTPNOQEASYAGZMOLZGYTLNRMGPRFYVJ",
"WMOZLANJZATXNZKPBXZMYRNXQELSYQGZMOLZGYTLNTMJPRFYZJ",
"ZYZZLANJZSTZZZKZBXZVYYNXQELZYRGZZVZZGZTLZTMMPVFZZJ",
"ZYZZLZNXZSUZZZZZBZZYYZVXZEMZYWGZZVZZZZTLZTMTZVFZZZ",
"ZYZZLZNXZSUZZZZZZZZZYZVXZEMZYZGZZZZZZZTZZTMTZVFZZZ",
"ZYZZLZNXZZUZZZZZZZZZZZVZZZMZYZZZZZZZZZZZZZMTZZFZZZ",
"ZYZZLZZXZZVZZZZZZZZZZZVZZZSZYZZZZZZZZZZZZZMTZZWZZZ",
"ZYZZLZZZZZVZZZZZZZZZZZVZZZSZYZZZZZZZZZZZZZZTZZWZZZ",
"ZYZZLZZZZZVZZZZZZZZZZZVZZZSZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZLZZZZZVZZZZZZZZZZZVZZZSZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZLZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZZZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZZZZZZZVZZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZYZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZVZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZTZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZWZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZWZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ" }
5)
    
{"BI", "AQ"}
Returns: { }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13678&pm=9759

Writer:

boba5551

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Search, Iteration, Sorting, String Manipulation