Problem Statement
You will be given a String[] grammar, where each element has the following format (quotes for clarity):
The lowercase letter e will have a special meaning. When in a derivable string it acts as any other lowercase letter, except it doesn't contribute to the length of the string. The significance of this will be evident after reading the next paragraph.
You will return a int[] with 2 elements. The first will be the length of the minimum length string derivable from grammar. The second will be the length of the maximum length string derivable from grammar. If the grammar derives no strings, set the first element to -1. If the grammar derives no strings or derives strings of unbounded length, set the second element to -1. As a reminder, the length of a string is the number of lowercase letters it contains, not counting e's. For the example above, you would return {1,-1}.
"C->X|X|...|X" or "C->X"Where C denotes a single capital letter, and X denotes a string of lowercase and/or capital letters. An example of valid input would be (quotes for clarity):
grammar = {"S->aSb|T",
"T->ab|ce"}
The first letter of the first element of grammar will denote the starting letter. A string y of lowercase letters is derivable from the given grammar if you can turn the starting letter into y using grammar rules. No capital letters may be present in a string derivable from a grammar. The grammar ruleS->aSb|Tmeans you can replace an S with either aSb or T. The string aacebb is derivable from the grammar above using the following rules:
S => aSb => aaSbb => aaTbb => aacebb.Note that each => represents a grammar rule being used.
The lowercase letter e will have a special meaning. When in a derivable string it acts as any other lowercase letter, except it doesn't contribute to the length of the string. The significance of this will be evident after reading the next paragraph.
You will return a int[] with 2 elements. The first will be the length of the minimum length string derivable from grammar. The second will be the length of the maximum length string derivable from grammar. If the grammar derives no strings, set the first element to -1. If the grammar derives no strings or derives strings of unbounded length, set the second element to -1. As a reminder, the length of a string is the number of lowercase letters it contains, not counting e's. For the example above, you would return {1,-1}.
Definition
- Class:
- GrammarTest
- Method:
- getSize
- Parameters:
- String[]
- Returns:
- int[]
- Method signature:
- int[] getSize(String[] grammar)
- (be sure your method is public)
Constraints
- grammar will contain between 1 and 26 elements inclusive.
- Each element of grammar will contain between 4 and 50 characters inclusive.
- Each element of grammar will conform to the description specified above.
- No two elements of grammar will have the same first character.
- Each element of the return value will be between -1 and 100000000 (100 million) inclusive.
Examples
{"S->aSb|T", "T->ab|ce"}Returns: { 1, -1 }From above.{"S->T|U", "T->aaa|aaaa|aaaaa|aaaaaa", "U->bbbbb|bbbbbb"}Returns: { 3, 6 }The shortest length of any derivable string is 3 (aaa). The longest length is 6 (aaaaaa or bbbbbb).{"R->AAAAAAAAAA", "A->BBBBBBBBBB", "B->CCCCCCCCCC", "C->DDDDDDDDDD", "D->EEEEEEEEEE", "E->FFFFFFFFFF", "F->GGGGGGGGGG", "G->HHHHHHHHHH", "H->z"}Returns: { 100000000, 100000000 }{"S->ABA", "A->q"}Returns: { -1, -1 }Note that there is no rule that begins with B. After applying the grammar rule S => ABA, we will never be able to remove the B, and thus cannot derive any strings.
Back to all problems