Sponsored
Sponsored
This approach uses dynamic programming with a hash map to store the possible jump lengths from each stone. Starting with the first stone and a jump of length 1, iterate through the stones, updating possible resultant jumps from each stone using the previously calculated jump lengths. Hash maps assist in efficiently checking if a stone can be reached from any prior stone using three different jump lengths.
Time Complexity: O(n^2), where n is the number of stones. This accounts for the iteration over the stones and the potential steps from each stone.
Space Complexity: O(n), used by the hash map to store possible jump lengths.
1function canCross(stones) {
2 const map = new Map();
3 for (let stone of stones) {
4 map.set(stone, new Set());
5 }
6 map.get(0).add(1);
7 for (let stone of stones) {
8 for (let step of map.get(stone)) {
9 for (let i of [step - 1, step, step + 1]) {
10 if (i > 0 && map.has(stone + i)) {
11 map.get(stone + i).add(i);
12 }
13 }
14 }
15 }
16 return map.get(stones[stones.length - 1]).size > 0;
17}This JavaScript solution is similar to the Python approach. It uses a map where each stone points to a set of potential jump lengths. It iterates through each stone and each of its jump lengths, then calculates new possible steps using the map to determine if those steps can land on any subsequent stone. If the last stone has valid jumps recorded, the frog can reach the end.
Use a depth-first search (DFS) approach combined with memoization to explore possible paths from the starting stone. The memoization helps in reducing repeated calculations by storing results of previously computed states (stone, jump_length). This approach recursively tries all possible jumps from a stone and checks if the end can be reached.
Time Complexity: O(n^2), potentially exploring all jump states for each stone.
Space Complexity: O(n^2), maintaining memoization of states.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4using namespace std;
5
class Solution {
public:
bool canCross(vector<int>& stones) {
unordered_map<int, unordered_set<int>> memo;
return dfs(stones, 0, 0, memo);
}
private:
bool dfs(vector<int>& stones, int idx, int jump, unordered_map<int, unordered_set<int>>& memo) {
if (idx == stones.size() - 1) return true;
if (memo[stones[idx]].count(jump)) return false;
for (int j = jump - 1; j <= jump + 1; ++j) {
if (j > 0) {
int next_pos = stones[idx] + j;
auto it = lower_bound(stones.begin(), stones.end(), next_pos);
if (it != stones.end() && *it == next_pos) {
int next_idx = it - stones.begin();
if (dfs(stones, next_idx, j, memo)) return true;
}
}
}
memo[stones[idx]].insert(jump);
return false;
}
};The C++ solution utilizes DFS with memoization. The canCross method initializes the process, calling a recursive dfs function starting from the first stone. This function tries all jump possibilities and checks if the final stone can be reached. The memo map tracks the states already visited. If the end stone is reached, it returns true. One unique aspect is using lower_bound to efficiently determine if a jump can directly land on a next stone.