C++ DFS + memory 33 ms


  • 0
    D
    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            if (stones.size() < 2) {
                return false;
            }
            
            int des = stones.back();
            unordered_map<int, unordered_set<int>> memo;
            //          start  steps
            unordered_set<int> stones_set(stones.begin(), stones.end());
            return dfs(stones_set, 0, 1, des, memo);
        }
    private:
        bool dfs(unordered_set<int> &stones, int start, int step, const int &des, unordered_map<int, unordered_set<int>> &memo) {
            if (memo.find(start) != memo.end() && memo[start].find(step) != memo[start].end()) {
                return false;
            }
            int next = start + step;
            if (next == des) {
                return true;
            }
            if (stones.find(next) == stones.end()) {
                memo[start].insert(step);
                return false;
            }
            
            if (dfs(stones, next, step + 1, des, memo) ||
                dfs(stones, next, step, des, memo) ||
                (step > 1 && dfs(stones, next, step - 1, des, memo))) {
                return true;    
            }
            memo[start].insert(step);
            return false;
        }
    };
    

Log in to reply
 

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