# Leetcode Frog Jump problem solution

In this Leetcode Frog Jump problem solution, A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

## Problem solution in Python.

```class Solution(object):
def canCross(self, stones):
self.memo = set()
target = stones[-1]
stones = set(stones)

res = self.bt(stones, 1, 1, target)
return res

def bt(self, stones, cur, speed, target):
# check memo
if (cur, speed) in self.memo:
return False

if cur==target:
return True

if cur>target or cur<0 or speed<=0 or cur not in stones:
return False
# dfs
candidate = [speed-1, speed, speed+1]
for c in candidate:
if (cur + c) in stones:
if self.bt(stones, cur+c, c, target):
return True

return False
```

## Problem solution in Java.

```public boolean canCross(int[] stones) {
if (stones.length == 0) return false;
int k = 1;
while(k < stones.length && stones[k] - stones[0] == 1) k++;
k--;

if (k == 0) return false;
return dfs(stones, k, 1, new HashSet());
}

boolean dfs(int[] stones, int i, int lastJump, Set set){
if (i == stones.length - 1) return true;
String key = i+"#"+lastJump;
if (set.contains(key)) return false;

boolean found = false;
int k = i+1;

for(; k < stones.length; k++){
if (stones[k] - stones[i] <= lastJump + 1 && stones[k] - stones[i] >= lastJump - 1){
boolean  reached =  dfs(stones, k, stones[k] - stones[i], set);
if (reached) return true;
found = true;
} else if (found) break;
}

return false;
}
}
```

## Problem solution in C++.

```class Solution {
public:
bool canCross(vector<int>& stones) {
map<int,set<int>>mp;
map<int,int>mp2;
for(int i=0;i<stones.size();i++)
{
mp[stones[i]].insert(0);
}
mp[0].insert(1);
for(int i=0;i<stones.size();i++)
{
set<int>vc = mp[stones[i]];
set<int>::iterator it = vc.begin();
while(it != vc.end())
{
int steps = (*it);
if(steps != 0 )
{
if(mp2[steps] == 0){
mp[stones[i]+steps].insert(steps-1);

mp[stones[i]+steps].insert(steps);

mp[stones[i]+steps].insert(steps+1);
mp2[steps]++;
}
}
it++;

}
mp2.clear();

}
int n = stones.size();
set<int>ans2 = mp[stones[n-1]];
if(ans2.size()==1)return false;
return true;

}
};
```

## Problem solution in C.

```bool canCrossWithStep(int* stones, int stonesSize, int t) {
if (stonesSize == 1) return true;
int m = -1, k = -1, p = -1;
for (int i = 1; i < stonesSize; i++) {
if (stones[i] == stones[0] + t + 1) p = i;
if (stones[i] == stones[0] + t ) k = i;
if (stones[i] == stones[0] + t - 1) m = i;
if (stones[i] > stones[0] + t + 1) break;
}
if (p != -1 && canCrossWithStep(stones + p, stonesSize - p, t + 1)) return true;
if (k != -1 && canCrossWithStep(stones + k, stonesSize - k, t)) return true;
if (m != -1 && canCrossWithStep(stones + m, stonesSize - m, t - 1)) return true;
return false;
}

bool canCross(int* stones, int stonesSize) {
if (stones[0] != 0 || stones[1] != 1) return false;
return canCrossWithStep(stones + 1, stonesSize - 1, 1);
}
```