Problem Statement
"UUURDR" means take 3 paces up, 1 pace to the right, 1 pace down, and another pace to the right.
Some trusted sources have informed you that certain parts of the directions are incorrect. This means if the directions incorrectly say 'U' at some point, it could either be 'D', 'L', or 'R'. Given the directions and the incorrect parts determine how many possible locations the treasure can be in. For example: directions = "UUR"
incorrect = {0,2}
This means that characters 0, and 2 in directions are false (directions are 0-based). Taking into account that character 0 ('U') and character 2 ('R') are incorrect, the possibly correct directions are:
"RUD","RUL","RUU","LUD","LUL","LUU","DUD","DUL","DUU"
The pictures below illustrate this data:
'P' marks the path taken 'X' marks possible locations with treasure 'S' marks the start point 'S' marks the start point path based on directions possible locations after correcting path ..PP. .X.X. ..P.. X.X.. ..S.. .XSX. ..... ..X.. ..... .....Even though there are 9 different paths that could be correct only 7 unique locations could have treasure so your method would return 7.
Create a class Treasure that contains the method numPlaces, which takes a String directions, and a
Definition
- Class:
- Treasure
- Method:
- numPlaces
- Parameters:
- String, int[]
- Returns:
- int
- Method signature:
- int numPlaces(String directions, int[] incorrect)
- (be sure your method is public)
Constraints
- directions will have length between 1 and 10 inclusive
- directions will only contain the characters 'U','D','L', and 'R' (quotes for clarity)
- incorrect will contain between 0 and k elements inclusive, where k is the length of directions
- Each element of incorrect will be between 0 and k-1 inclusive, where k is the length of directions
- incorrect will contain no duplicate elements
Examples
"UUR"
{0, 2}
Returns: 7
This is the example above.
"RRRUUURRL"
{}
Returns: 1
The path is completely correct so there is only one possible treasure location.
"RRRRRRRRRR"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 66
This example tests the speed of your code.
"ULDDUR"
{3, 2}
Returns: 6
"RRULDURR"
{0, 4, 5}
Returns: 13
"RULDRULDRU"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 103
"RULDRULDRU"
{}
Returns: 1
"UUUUUUUUUU"
{}
Returns: 1
"UUUUUUUUUU"
{9, 8, 7, 0, 1, 2, 3, 4, 5, 6}
Returns: 66
"RLRLRLRLRL"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 91
"RLUDRULDRD"
{0, 2, 4, 6, 8}
Returns: 28
"LLLLLLLLLL"
{8, 1, 2, 0, 4, 3, 9}
Returns: 36
"U"
{}
Returns: 1
"U"
{0}
Returns: 3
"RL"
{0, 1}
Returns: 7
"LLLRRRLRLR"
{0, 1, 2, 3, 4, 9, 8, 7, 6, 5}
Returns: 91
"RULDU"
{0, 1, 2, 4}
Returns: 20
"RUDDDDDDUU"
{1, 2, 3, 5, 7, 9}
Returns: 36
"UDDUR"
{3, 2}
Returns: 7
"UUR"
{1}
Returns: 3
"RRR"
{}
Returns: 1
"RRRRRRRRRR"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 66
"DRLUDRRLDU"
{0, 3, 2, 1, 4, 5, 6, 8, 9, 7}
Returns: 103
"RRRRRRRR"
{0, 1, 5, 3, 4}
Returns: 21
"RRRRRRRRRR"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 66
"UUDUUUUUUU"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 75
"RRRRURRRLR"
{1, 9, 0, 8, 7, 3, 2, 5, 4, 6}
Returns: 83
"RRRRRLRRRR"
{1, 5, 0, 9, 4, 2, 3, 8, 7, 6}
Returns: 75
"ULDDUR"
{3, 2}
Returns: 6
"UDRLRDU"
{0, 2, 3, 4}
Returns: 20