C++, 9ms, dfs solution


  • 0

    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();   
    }

  • 0
    Y

    Your solution is TLE now.


  • 0

    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();        
    }

  • 0
    C

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


  • 0
    S

    @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;
    }

Log in to reply
 

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