Problem Statement | |||||||||||||
A context free grammar is a set of words represented by a set of derivation rules, each written
as If you have several rules for the same nonterminal: There is a special nonterminal called a seed. Sequences of terminals that can be derived from the seed are the words that belong to the set described by the grammar. In this problem we will use uppercase letters exclusively for nonterminals and lowercase letters for terminals. For example, this specification: A parsing tree in this context is a tree whose root node is the seed. The children of each nonterminal node are the symbols of the expression derived from that nonterminal using one of the derivation rules. These children are ordered from left to right. If read in that order, the leaves of a parsing tree form the parsed word. A terminal node is further to the left than another one if the path that leads to it from the first common ancestor begins with a branch that is further to the left in the rule used. The parsing tree for the string bdd in the above specification is: A / \ B D | / \ b d D | dNow, in this case this is the only possible parsing tree for that string, but the string bbd has two parsing trees: A / \ B D / \ | b B d | band A / \ B D / \ | B b d | b To avoid having infinite parsing trees, no expression on the right side of a rule will be just one nonterminal. You are given the set of rules as a String[], where each element is formatted as described above, along with a seed and a word. Return the number of distinct parsing trees for the given word. If there are more than 1000000000 (109) parsing trees, return -1. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | Two parsing trees are considered different if they have different tree structures, or if they have the same structure, but at least one node used a different rule to derive its children than the corresponding node in the other tree. | ||||||||||||
- | According to the above note, if there are multiple equal rules (same nonterminal and same expression), there can be trees that are different even though have the same exact nodes and structure. See example 3 for further clarification. | ||||||||||||
- | All uppercase letters are considered nonterminals even if they do not appear on the left side of any rule. | ||||||||||||
- | When multiple expressions separated by pipes appear in a single line, each one still counts as a distinct rule (see example 5). | ||||||||||||
Constraints | |||||||||||||
- | word will contain between 1 and 35 characters, inclusive. | ||||||||||||
- | Each character of word will be a lowercase letter ('a'-'z'). | ||||||||||||
- | seed will be an uppercase letter ('A'-'Z'). | ||||||||||||
- | rules will contain between 1 and 50 elements, inclusive. | ||||||||||||
- | Each element of rules will contain between 1 and 50 characters, inclusive. | ||||||||||||
- | Each element of rules will start with an uppercase letter, followed by " ::= ", followed by a list of one or more expressions separated by " | ", where each expression is a non-empty sequence of lowercase and uppercase letters ('a'-'z' and 'A'-'Z'). | ||||||||||||
- | No expression on the right side of a rule will be just one uppercase letter. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
| |||||||||||||
4) | |||||||||||||
| |||||||||||||
5) | |||||||||||||
|