DerivationDisplay | Topcoder Archive

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

"aaabb"

Returns: {"S", "T", "aTb", "aaTbb", "aaAbb", "aaabb" }

The example above.

```
"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.

"baabba"

Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

```
"a"
```
```
Returns: {"S", "T", "A", "a" }
```
```
"b"
```
```
Returns: {"S", "T", "B", "b" }
```

"aabbbbbbbb"

Returns: {"S", "T", "aTb", "aaTbb", "aaBbb", "aabBbb", "aabbBbb", "aabbbBbb", "aabbbbBbb", "aabbbbbBbb", "aabbbbbbbb" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.