Leetcode Frog Jump problem solution

YASH PAL,

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.

Leetcode Frog Jump problem solution

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

        self.memo.add((cur,speed))
        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;
        }
        
        set.add(key);
        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);
}

coding problems