TopCoder problem "WordPuzzle" used in TCCC '04 Wildcard (Division I Level One)



Problem Statement

    

In some popular word puzzles from newspapers, you are to convert a word into another word by either swapping letters, or changing one letter to another. However, one constraint is that the characters formed by each move MUST be a real word.

Your method will be given a String source that should be converted to a String target. You will also be given a String[] dictionary, where each element is a word you are allowed to use in the conversion. At each step, you can either swap two (not necessarily adjacent) characters in a word, or change one letter in a word. The new word must be either target or one of the words from dictionary. The return value will be a String[] containing the words used to do the conversion, in the order they were used. The first element in the return value should be source, the last element should be target. If multiple ways exist to convert from one word to the other, you should return the one with the smallest number of intermediate words. If two sequences exist that have the same number of intermediate words, return the sequence which is smallest lexicographically. Sequence A is lexicographically smaller than sequence B if the first string A[i] that differs from B[i] is lexicographically smaller than B[i]. String A[i] is lexicographically smaller than B[i] if the first character A[i][j] that differs from B[i][j] comes before B[i][j] alphabetically. All words in the input will be the same length. If no conversion is possible, return an empty String[].

 

Definition

    
Class:WordPuzzle
Method:getConversions
Parameters:String[], String, String
Returns:String[]
Method signature:String[] getConversions(String[] dictionary, String source, String target)
(be sure your method is public)
    
 

Notes

-The words in the input might or might not be actual English words or words from any other language. See example 3.
 

Constraints

-dictionary has between 1 and 50 elements, inclusive.
-source has between 4 and 50 characters, inclusive.
-target has the same number of characters as source.
-All elements in dictionary have the same number of characters as source.
-source, target, and all elements of dictionary will consist only of lowercase letters ('a'-'z').
-source will not be the same as target.
-source and target will not appear in dictionary.
-There will be no repeated elements in dictionary.
 

Examples

0)
    
{"fowl","foal","loaf","load","loan","loon","toon"}
"foul"
"tool"
Returns: { "foul",  "foal",  "loaf",  "loan",  "loon",  "toon",  "tool" }
Note that although in the given list of words, each element can achieve the next, you can skip over "fowl" and "load" since you can go directly from "foul" to "foal", and directly from "loaf" to "loan".
1)
    
{"stew","wets"}
"stow"
"west"
Returns: { }
Only two letters can be swapped at once.
2)
    
{"flew", "slew", "stew", "stow"}
"flow"
"slow"
Returns: { "flow",  "slow" }
In this conversion, no words from the dictionary were necessary.
3)
    
{"tsray","trsay","trasy"}
"stray"
"trays"
Returns: { "stray",  "tsray",  "trsay",  "trasy",  "trays" }
Note that you cannot simply remove the 's' and insert it at the end.
4)
    
{"toon","loot"}
"loon"
"tool"
Returns: { "loon",  "loot",  "tool" }

The following is also a conversion with three words, but is lexicographically larger than the answer:

loon -> toon -> tool

5)
    
{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaay",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaw",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaav",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaau",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaat",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaas",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaar",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaq",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaap",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaao",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaan",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaam",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaal",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaak",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaj",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaai",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaag",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaf",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaae",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "yaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "waaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "vaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "uaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "taaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "saaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "raaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "qaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "paaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "oaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "maaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "laaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "kaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "jaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "iaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "haaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "gaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "faaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "eaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "daaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz"}
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz"
Returns: 
{ "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
 "zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5079&pm=2298

Writer:

schveiguy

Testers:

lbackstrom , brett1479 , vorthys

Problem categories:

Dynamic Programming, Recursion, Search