c++ DFS using memo


  • 1
    L
    class Solution {
      public:
        bool canCross(vector<int> &stones) {
            unordered_map<int, unordered_map<int, bool>> dir;
            return helper(stones, 0, 0, dir);
        }
        bool helper(vector<int> &stones, int start, int k,
                    unordered_map<int, unordered_map<int, bool>> &dir) {
            if (start == stones.size() - 1) {
                return true;
            }
            if (dir.count(start) && dir[start].count(k)) {
                return dir[start][k];
            }
            for (int step = max(k - 1, 1); step <= k + 1; step++) {
                for (int i = start + 1; i < stones.size(); i++) {
                        if (stones[start] + step == stones[i] &&
                            helper(stones, i, step, dir)) {
                            dir[start][k] = true;
                            return true;
                        }
                }
            }
            dir[start][k] = false;
            return false;
        }
    };
    

  • 1
    L

    another solution modified from https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations?page=1
    Here is the the solution of c++

    class Solution {
      public:
        bool canCross(vector<int> &stones) {
            unordered_map<int, unordered_set<int>> dir;
            for (auto stone : stones) {
                dir[stone] = unordered_set<int>{};
            }
            dir[0].insert(1);
            for (int i = 0; i < stones.size(); i++) {
                for (int step : dir[stones[i]]) {
                    int reach = step + stones[i];
                    if (reach == stones[stones.size() - 1]) {
                        return true;
                    }
                    if (dir.count(reach)) {
                        for (int j = max(step - 1, 1); j <= step + 1; j++) {
                            dir[reach].insert(j);
                        }
                    }
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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