TopCoder problem "DerivationDisplay" used in SRM 234 (Division II Level Three)



Problem Statement

    
  S ::= T | bUa
  T ::= aTb | A | B
  U ::= aU | bU | a | b
  A ::= aA | a
  B ::= bB | b
Displayed above is a Context-Free Grammar (CFG). You begin with the string (quotes for clarity) "S", and apply replacement rules until your resulting string no longer contains any capital letters. The first line above says that S can be replaced with T or bUa. The other lines are similar. You will return a sequence of strings, beginning with "S" and ending with input, where each successive sequence element results from applying one of the replacement rules above. For example, if input is "aaabb" then you will return 
 {"S","T","aTb","aaTbb","aaAbb","aaabb"}
 

Definition

    
Class:DerivationDisplay
Method:getDerivation
Parameters:String
Returns:String[]
Method signature:String[] getDerivation(String input)
(be sure your method is public)
    
 

Constraints

-input will contain between 1 and 50 characters inclusive.
-Each character in input will be 'a' or 'b'.
-There will be exactly one solution.
 

Examples

0)
    
"aaabb"
Returns: {"S", "T", "aTb", "aaTbb", "aaAbb", "aaabb" }
The example above.
1)
    
"bbba"
Returns: {"S", "bUa", "bbUa", "bbba" }
In the first step, S must be replaced with bUa in order to derive this string. Then the 2 inner b's are added.
2)
    
"baabba"
Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }
3)
    
"a"
Returns: {"S", "T", "A", "a" }
4)
    
"b"
Returns: {"S", "T", "B", "b" }
5)
    
"aabbbbbbbb"
Returns: 
{"S",
"T",
"aTb",
"aaTbb",
"aaBbb",
"aabBbb",
"aabbBbb",
"aabbbBbb",
"aabbbbBbb",
"aabbbbbBbb",
"aabbbbbbbb" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6533&pm=4021

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

String Parsing