Problem Statement |
| | Some alien civilization has a quite strange language. Each word has length wordLength and consists of only 'A' and 'B' characters. Some sequences of A's and B's are forbidden (by ancient tradition), and do not appear as a substring of any valid word. Any word that does not contain a forbidden substring is valid. The set of forbidden substrings is given in the String[] forbiddenSubstrings. Each element of forbiddenSubstrings contains 'A', 'B' or '?' characters, where '?' means any single character. For example, if forbiddenSubstrings contains the element "ABB?B", then both "ABBAB" and "ABBBB" are forbidden substrings.
The alien dictionary contains all valid alien words in alphabetical order.
Each page of the dictionary contains exactly one word. Pages are numbered starting from 0. Given a int[] wordNumbers, return a String[] containing the same number of elements as wordNumbers, where the i-th element is the word written on page wordNumbers[i] of the dictionary or "NO PAGE" (quotes for clarity) if there is no such page in the dictionary. |
| |
Definition |
| | | Class: | AlienDictionary | | Method: | getWords | | Parameters: | int, String[], int[] | | Returns: | String[] | | Method signature: | String[] getWords(int wordLength, String[] forbiddenSubstrings, int[] wordNumbers) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | wordLength will be between 1 and 50, inclusive.
|
| - | wordNumbers will contain between 1 and 50 elements, inclusive.
|
| - | Each element of wordNumbers will be between 0 and 1,000,000,000, inclusive.
|
| - | forbiddenSubstrings will contain between 0 and 50 elements, inclusive.
|
| - | Each element of forbiddenSubstrings will contain between 1 and 17 characters, inclusive.
|
| - | Each element of forbiddenSubstrings will contain only characters 'A', 'B' or '?'.
|
| - | All elements of forbiddenSubstrings will contain the same number of characters.
|
| |
Examples |
| 0) | |
| | 5 | {"?AA","ABB"} | {4,12,0,6,9} |
| Returns: {"BBBAB", "NO PAGE", "AABAB", "BBBBB", "NO PAGE" } | | Invalid combinations are "AAA", "BAA" and "ABB". |
|
|
| 1) | |
| | | Returns: {"AAB", "BAA", "BBB", "BAB", "AAB" } | |
|
| 2) | |
| | | Returns: {"ABBB", "BBBA", "NO PAGE", "BABB", "NO PAGE" } | |
|
| 3) | |
| | 10 | {"BABB?","??A?B","A?AAA","A??AB","?A??A"} | {0,1} |
| Returns: {"AABBBABABA", "AABBBBABAB" } | |
|