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.
1def canCross(stones):
2 if stones[1] != 1:
3 return False
4 stone_dict = {stone: set() for stone in stones}
5 stone_dict[0].add(1)
6 for stone in stones:
7 for jump_length in stone_dict[stone]:
8 for step in [jump_length - 1, jump_length, jump_length + 1]:
9 if step > 0 and (stone + step) in stone_dict:
10 stone_dict[stone + step].add(step)
11 return len(stone_dict[stones[-1]]) > 0The solution starts by checking if the first jump to the second stone is valid. It initializes a map, stone_dict, to keep track of possible jump lengths for each stone. It iterates through each stone and for each available jump length, calculates possible steps (current, one less, and one more unit) and checks if they can land on a valid stone. If so, it records the step in the map. The function then checks if there are any valid jumps recorded for the last stone.
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.