# C++, 9ms, dfs solution

• straightforward dfs solution, just try all 3 jumps to see whether can arrive at the last stone.

``````bool help(vector<int>& stones,int start,int k){
if (start==stones.size()-1) return true;
for (int i=start+1;i<stones.size();i++){
if (stones[i]-stones[start]<k-1) continue;
if (stones[i]-stones[start]>k+1) return false;
if (help(stones,i,stones[i]-stones[start])) return true;
}
return false;
}

bool canCross(vector<int>& stones) {
if (stones.size()<=1) return 1;
int start = 0,k = 0;   // k is the steps when jumping to current stone.
return help(stones,start,k);
}
``````

I also tried the O(N^2) DP solution, however, it takes much longer time. Maybe there are two much wasted checks.

``````bool canCross(vector<int>& stones) {
if (stones.size()<=1) return true;
unordered_map<int,unordered_set<int>> jumps;
for (auto&x:stones){
jumps[x]=unordered_set<int>();
}
jumps[0].insert(0);
for (int i=0;i<stones.size();i++){
if (jumps[stones[i]].empty()) continue;
else{
for (auto &x:jumps[stones[i]]){
if (x>0) jumps[stones[i]+x].insert(x);
jumps[stones[i]+x+1].insert(x+1);
if (x-1>0) jumps[stones[i]+x-1].insert(x-1);
}
}
}
return !jumps[stones.back()].empty();
}``````

• Your solution is TLE now.

• well, the dp solution still works.

``````bool canCross(vector<int>& stones) {
if (stones.size()<=1) return true;
unordered_map<int,unordered_set<int>> jumps;
for (auto&x:stones){
jumps[x]=unordered_set<int>();
}
jumps[0].insert(0);
for (int i=0;i<stones.size();i++){
if (jumps[stones[i]].empty()) continue;
else{
for (auto &x:jumps[stones[i]]){
if (x>0) jumps[stones[i]+x].insert(x);
jumps[stones[i]+x+1].insert(x+1);
if (x-1>0) jumps[stones[i]+x-1].insert(x-1);
}
}
}
return !jumps[stones.back()].empty();
}``````

• Thanks for your answer.What's the time complexity of your DFS solution?

• @Dragon.PW
your code can be more concise

``````bool canCross(vector<int>& stones) {
int n = stones.size();
if (n <= 1) return true;

// jump steps of different stones
unordered_map<int, unordered_set<int>> jumps;
jumps[0].insert(0);

for (int i = 0; i < n; ++i) {
if (!jumps.count(stones[i])) continue;

for (auto x : jumps[stones[i]]) { // different steps
if (x > 0) jumps[stones[i] + x].insert(x);
if (x - 1 > 0) jumps[stones[i] + x - 1].insert(x - 1);
jumps[stones[i] + x + 1].insert(x + 1);
}
}

return jumps.count(stones.back()) > 0;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.