Frog Jump LeetCode solution in Java

1
class Solution {
2
  static boolean flag =
3
      false; // If flag is true no more operations in recursion, directly return statement
4

5
  public boolean canCross(int[] stones) {
6
    int i = 0; // starting stone
7
    int k = 1; // starting jump
8
    flag = false;
9
    return canBeCrossed(stones, k, i);
10
  }
11

12
  public boolean canBeCrossed(int[] stones, int k, int i) {
13
    if (!flag) { // If flag is false
14
      if (stones[i] + k
15
          == stones[
16
              stones.length
17
                  - 1]) { // If frog do 'k' jump from current stone lands on last stones, no more
18
        // recusive calls and return true
19
        flag = true;
20
        return true;
21
      }
22
      // If frog do 'k' jump from current stone crosses last stone or not able to reach next stone
23
      // return false
24
      if ((stones[i] + k > stones[stones.length - 1]) || (stones[i] + k < stones[i + 1]))
25
        return false;
26
      int temp = i + 1; // identify which next stone frog can reach
27
      // Find untill which stone frog can jump
28
      // So jump from current stone not greater than next possible stone exit loop
29
      while (stones[i] + k > stones[temp]) temp++;
30
      // If loop exited 2 condition possible
31
      // jump from current stone is reached next possible stone
32
      // or not
33

34
      // If next possible stone reached
35
      // then do all possible jumps from this stone
36
      // the current stone is 'temp'
37
      // possible jumps are 'k-1', k, 'k+1'
38
      if (stones[i] + k == stones[temp])
39
        return (canBeCrossed(stones, k + 1, temp)
40
            || canBeCrossed(stones, k, temp)
41
            || canBeCrossed(stones, k - 1, temp));
42

43
      // If next possible stone not reached means jump from the current stone can't reach any stone
44
      // hence return false
45
      else return false;
46
    } else return true;
47
  }
48
}