TopCoder problem "AnagramCompletion" used in TCHS SRM 24 (Division I Level Two)



Problem Statement

    

Two words are said to be anagrams if one word can be formed by rearranging the letters of the other word. For example, "AABC" and "CABA" are anagrams.

You will be given two Strings, word1 and word2, representing two words. These two strings will contain only uppercase letters ('A'-'Z') and '.' characters which denote missing letters. Replace the '.' characters with uppercase letters such that the two words become anagrams and return the result as a String[] containing exactly two elements. The first element should correspond to word1 and the second element should correspond to word2. If there are multiple possible return values, choose the one in which the first element comes first alphabetically. If ties still exist, choose the one among them in which the second element comes first alphabetically. If it is impossible to make the two words into anagrams, return an empty String[]. Note that two equal words are considered anagrams.

 

Definition

    
Class:AnagramCompletion
Method:complete
Parameters:String, String
Returns:String[]
Method signature:String[] complete(String word1, String word2)
(be sure your method is public)
    
 

Constraints

-word1 will contain between 1 and 50 characters, inclusive.
-word2 will contain the same number of characters as word1.
-word1 and word2 will contain only uppercase letters ('A'-'Z') and '.' characters.
-There will be at least one '.' in at least one of the two words.
 

Examples

0)
    
"AB.AC."
"ABD..E"
Returns: {"ABDACE", "ABDACE" }
The letters 'D' and 'E' appear in the second word but not in the first one, so we place them in the two empty spots. Similarly the letter 'C' must be present in the second word. The letter 'A' must appear a second time in the second word. Ties are broken alphabetically.
1)
    
"ABC..."
"DEF..."
Returns: {"ABCDEF", "DEFABC" }
2)
    
"......"
"......"
Returns: {"AAAAAA", "AAAAAA" }
All the letters are missing, so we can replace them all with the letter 'A'.
3)
    
"TOPCODER"
"D.E..TR."
Returns: {"TOPCODER", "DCEOOTRP" }
4)
    
"ABC."
"DEF."
Returns: { }
Each word is missing three letters from the other word, but there is only one empty spot in each of them.
5)
    
"TEFAT..PVSKKJT.QBJEB..NPN..NBL"
"...B...E.ND.LNE...HW.ANTB.TKBD"
Returns: {"TEFATAAPVSKKJTAQBJEBDDNPNHWNBL", "AAABFJJEKNDPLNEPQSHWTANTBVTKBD" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10076&pm=7271

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy, Simple Search, Iteration, String Manipulation