Q64 Frog Jump - LeetCode 403
Sun Apr 02 2023 17:03:17 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public boolean canCross(int[] stones) {
/* Q64 of dp playlist , in this question we need to store the jumps which
has been made from the previous stone for that we make a HM<stones , HS>
to store the allowed jumps
we traverse the array and keep updating the next stones allowed jumps,
if we end up on any stone which has its jumps hashset = 0 we return false
if we end on last stone we return true;
*/
//make a hashmap to store allowed jumps
HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
int n = stones.length;
//fill the hashmap and initialise the HS
for(int i = 0 ; i < n ; i++)
map.put(stones[i] , new HashSet<>());
//adding jumps for 0th and 1st stone;
map.get(0).add(1);
//traverse the array
for(int i = 0 ; i < n ; i++){
//taking out allowed jumps
HashSet<Integer> jumps = map.get(stones[i]);
//check all jumps in jumps hashset
for(int jump : jumps){
System.out.print(" " + stones[i] +" "+ jump+ "\n" );
boolean validJump = map.containsKey(stones[i] + jump);
//if after jumping we end on a valid stone update the jumps of
//the valid stone
if(validJump == true){
HashSet<Integer> nextStone = map.get(stones[i] + jump);
nextStone.add(jump);
nextStone.add(jump + 1);
//we cannot add 0 jumps
if(jump != 1)
nextStone.add(jump - 1);
map.put(stones[i] + jump , nextStone);
}
}
}
if(map.get(stones[n-1]).size() > 0){
// System.out.println(map);
return true;
}
else{
// System.out.println(map);
return false;
}
}
}
content_copyCOPY
https://leetcode.com/problems/frog-jump/
Comments