Problem Statement |
| | Every big project contains multiple scripts, each of which may require access to other scripts within the project. Each script contains an import list containing zero or more other scripts. A script has access to all the scripts in its import list, and it also has access to all the scripts that the scripts in its import list have access to. More formally, a script A has access to a script B if and only if there exists a sequence of scripts S[0] = A, S[1], ..., S[k] = B, where k >= 1 and for each i, where 0 <= i < k, script S[i] contains script S[i+1] in its import list. There is an important restriction on the usage of import lists: a script must not have access to itself.
You are given the requirements for your project as a String[] requires. It contains exactly N elements, where N is the number of scripts in the project. Character j of element i of requires is 'Y' if script i must have access to script j, and 'N' otherwise. You must generate the import list for each script in such a way that all the requirements are satisfied. This means that each script must have access to all its required scripts, and not have access to unrequired scripts (including itself). The total number of scripts in all the import lists of all the scripts must be as small as possible (if several import lists contain the same script, each occurrence of that script counts toward the total). Return a int[] containing exactly N elements, where element i is the number of scripts in the import list for script i. |
| |
Definition |
| | | Class: | ImportsList | | Method: | importsCount | | Parameters: | String[] | | Returns: | int[] | | Method signature: | int[] importsCount(String[] requires) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Under the given constraints, there always exists exactly one way to generate import lists with the smallest total number of scripts. |
| |
Constraints |
| - | requires will contain between 1 and 50 elements, inclusive.
|
| - | Each element of requires will contain exactly N characters 'Y' or 'N', where N is the number of elements in requires.
|
| - | If the j-th character in the i-th element of requires is 'Y' and the k-th character in the j-th element of requires is 'Y', then the k-th character in the i-th element of requires will be 'Y'.
|
| - | The i-th character in i-th element of requires will be 'N'. |
| |
Examples |
| 0) | |
| | | Returns: {0, 0, 0 } | | None of these scripts require other scripts, so no imports are needed. |
|
|
| 1) | |
| | {"NYYY"
,"NNYY"
,"NNNY"
,"NNNN"} |
| Returns: {1, 1, 1, 0 } | | Each script needs to import the next one. |
|
|
| 2) | |
| | {"NNNNY"
,"NNNNY"
,"YNNNY"
,"NNNNN"
,"NNNNN"} |
| Returns: {1, 1, 1, 0, 0 } | | Script 2 must import script 0 and each of the scripts 0 and 1 must import script 4. |
|
|
| 3) | |
| | {"NYYNYNYYYNYYNYNN"
,"NNNNNNNNNNNNNNNN"
,"NNNNNNNNNNYNNNNN"
,"NNNNNNNNNYNNYNNN"
,"NYNNNNYNNNYYNNNN"
,"NYNNYNYNYNYYNNNN"
,"NNNNNNNNNNYNNNNN"
,"NNYNNNYNYNYNNNNN"
,"NNNNNNYNNNYNNNNN"
,"NNNNNNNNNNNNYNNN"
,"NNNNNNNNNNNNNNNN"
,"NNNNNNNNNNNNNNNN"
,"NNNNNNNNNNNNNNNN"
,"NNNNNNYNNNYNNNNN"
,"YYYYYNYYYYYYYYNY"
,"NYYYNNYNNYYNYYNN"} |
| Returns: {3, 0, 1, 1, 3, 2, 1, 2, 1, 1, 0, 0, 0, 1, 2, 4 } | |
|