C++ Pure recursive solution but it's is fast (16 ms)


  • 0
    Q

    The key point for this short time is that I scan the stones input first and find the max gap first, and use n(n+1)/2 formula to test whether we can jump across it at that moment.
    I tried to use DP[1100][1100] based on previous stone and current stone, which implies last jump distance, but it doesn't shorten the time.

    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            if(stones.size() < 2 || stones[1] != 1) return false;
            int maxGap = 0, maxGapIndex = 0;
            for(int i = 1; i < stones.size(); ++i) {
                if(stones[i]-stones[i-1] > maxGap) {
                    maxGap = stones[i]-stones[i-1];
                    maxGapIndex = i;
                }
            }
            if(maxGap > (maxGapIndex)*(maxGapIndex+1)/2) return false;  //index starts with 0, so to stones[3] we have 3 jumps max
            return dfs(stones, 0, 1);
        }
        bool dfs(vector<int>& stones, int prevLoc, int curLoc) {
            // if(curLoc == stones.size()-1) {
            //     return true;
            // }
            int lastJump = stones[curLoc]-stones[prevLoc];
            if( (stones[curLoc]+lastJump == stones.back()) || (stones[curLoc]+lastJump-1 == stones.back())
               || (stones[curLoc]+lastJump+1 == stones.back()) ) {
               return true; 
            }      
            auto it = lower_bound(stones.begin(), stones.end(), stones[curLoc]+lastJump);
            if(it != stones.end() && *it == stones[curLoc]+lastJump) {
                if( dfs(stones, curLoc, it-stones.begin())) return true; 
            }
            if(lastJump != 1) {
                it = lower_bound(stones.begin()+curLoc, stones.end(), stones[curLoc]+lastJump-1);
                if(it != stones.end() && *it == stones[curLoc]+lastJump-1) {
                    if( dfs(stones, curLoc, it-stones.begin())) return true;
                }
            }
            it = lower_bound(stones.begin()+curLoc, stones.end(), stones[curLoc]+lastJump+1);
            if(it != stones.end() && *it == stones[curLoc]+lastJump+1) {
                if( dfs(stones, curLoc, it-stones.begin()))  return true;
            }
            return false;
        }
    };

  • 0
    Q

    Modified version with memorization but no early-gap-detection, 56 ms

    class Solution {
    private:
        int maxGap, maxGapIndex;
        char pass[1100][1100];    
    public:
        bool canCross(vector<int>& stones) {
            if(stones.size() < 2 || stones[1] != 1) return false;
            // maxGapIndex = 0;
            // maxGap = 0;
            // for(int i = 1; i < stones.size(); ++i) {
            //     if(stones[i]-stones[i-1] > maxGap) {
            //         maxGap = stones[i]-stones[i-1];
            //         maxGapIndex = i;
            //     }
            // }
            // if(maxGap > (maxGapIndex)*(maxGapIndex+1)/2) return false;  //index starts with 0, so to stones[3] we have 3 jumps max
            return dfs(stones, 0, 1);
        }
        bool dfs(vector<int>& stones, int prevLoc, int curLoc) {
            if(pass[prevLoc][curLoc] == -1 ){
                return false;
            }
            int lastJump = stones[curLoc]-stones[prevLoc];
            if( (stones[curLoc]+lastJump == stones.back()) || (stones[curLoc]+lastJump-1 == stones.back())
               || (stones[curLoc]+lastJump+1 == stones.back()) ) {
               return true; 
            }      
            for(int jump = lastJump -1; jump <= lastJump+1; ++jump) {
                if(jump == 0) continue;
                auto it = lower_bound(stones.begin(), stones.end(), stones[curLoc]+jump);
                if(it != stones.end() && *it == stones[curLoc]+jump) {
                    if( dfs(stones, curLoc, it-stones.begin())) return true; 
                }
            }
            pass[prevLoc][curLoc] = -1;
            return false;
        }
    };

Log in to reply
 

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