forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_403.java
46 lines (42 loc) · 1.5 KB
/
_403.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.fishercoder.solutions;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class _403 {
public static class Solution1 {
/**
* Reference: https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations/2
* and https://leetcode.com/articles/frog-jump/#approach-5-using-dynamic-programmingaccepted
*/
public boolean canCross(int[] stones) {
if (stones.length == 0) {
return true;
}
Map<Integer, Set<Integer>> map = new HashMap<>(stones.length);
map.put(0, new HashSet<>());
map.get(0).add(1);
for (int i = 1; i < stones.length; i++) {
map.put(stones[i], new HashSet<>());
}
for (int i = 0; i < stones.length; i++) {
int stone = stones[i];
for (int step : map.get(stone)) {
int reach = step + stone;
if (reach == stones[stones.length - 1]) {
return true;
}
Set<Integer> set = map.get(reach);
if (set != null) {
set.add(step);
if (step - 1 > 0) {
set.add(step - 1);
}
set.add(step + 1);
}
}
}
return false;
}
}
}