TopCoder problem "LeftmostDerivation" used in TCO04 Wildcard (Division I Level Two)

Problem Statement

In a Context-Free Grammar, strings are transformed into other strings during a process called a derivation. In our notation, one step of a derivation occurs when an uppercase letter ('A'-'Z') is turned into a string (possibly empty) of uppercase and lowercase letters ('A'-'Z', 'a'-'z'). For example,

     ZaBcD -> ZagHgcD -> ZagHgcF -> ZaggcF -> Zaggcq

is a derivation transforming ZaBcD into Zaggcq. A derivation is called leftmost if every derivation step replaces the leftmost uppercase letter. Assuming all valid derivation steps are at your disposal, return the leftmost derivation with the smallest number of steps transforming start into finish. Since all possible derivation rules can be used, during each step, choose the leftmost capital letter, and change it to whichever string you want. If there are multiple possible smallest leftmost derivations, return one that comes first lexicographically. Here smallest is measured by the number of steps. To compare two derivations lexicographically, concatenate all of their intermediate strings, and then compare them. As in ASCII, uppercase letters occur lexicographically before lowercase letters. The returned value should be a String[] containing the sequence of intermediate strings, in the order they are created. Element 0 must be start, and the last element must be finish (see the examples for further clarification). If no leftmost derivation is possible, return an empty String[].

Definition

Class:	LeftmostDerivation
Method:	getDeriv
Parameters:	String, String
Returns:	String[]
Method signature:	String[] getDeriv(String start, String finish)
(be sure your method is public)

Constraints

start will contain between 1 and 50 characters inclusive.

Each character in start will be an uppercase or lowercase letter ('A'-'Z','a'-'z').

finish will contain between 1 and 50 characters inclusive.

Each character in finish will be an uppercase or lowercase letter ('A'-'Z','a'-'z').

start and finish will be distinct.

Examples

"ZaBcD"

"Zaggcq"

Returns: { }

Although a derivation was shown in the problem statement, there is no leftmost derivation that works.

"AH"

"ABCDEFGH"

Returns: { "AH",  "ABCDEFGH" }

Here we replace A with ABCDEFG.

"ABC"

"abc"

Returns: { "ABC",  "BC",  "C",  "abc" }

There are numerous leftmost derivations that take 3 steps, so return the one that occurs first lexicographically.

"AaA"

"aAaa"

Returns: { "AaA",  "aA",  "aAaa" }

Firstly, we delete the leftmost A by replacing it with the empty string. Next we replace the remaining A with Aaa.

"AaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa"

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

Returns: 
{ "AaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaAaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaaAaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaaaAaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaaaaAaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaaaaaAaAaAaAaAa",
 "aaaaaaaaaaaaaaaaaaaaAaAaAaAa",
 "aaaaaaaaaaaaaaaaaaaaaAaAaAa",
 "aaaaaaaaaaaaaaaaaaaaaaAaAa",
 "aaaaaaaaaaaaaaaaaaaaaaaAa",
 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5885&pm=3051

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Yarin

Problem categories:

String Parsing