DFS cannot pass after test cases changed, but this can with cached table, 88ms


  • 0
    0

    recursive with cached intermediate results

    struct pHash {
        size_t operator()(const pair<int, int>& k) const {
            return hash<long long>()((long long)k.first << 32 | k.second);
        }
    };
    
    class Solution {
    public:
        bool canCross(vector<int>& stones) {
            unordered_set<int> table;
            for (int p : stones) table.insert(p);
            unordered_map<pair<int, int>, bool, pHash> dyn;
            return canCross(table, 0, 1, stones[stones.size() - 1], dyn);
        }
    
        template<typename T1,  typename T2>
        bool canCross(const T1& table, int pos, int step, int dest, T2& dyn) {
            if (pos == dest) return true;
            if (step <= 0) return false;
            if (table.count(pos + step) == 0) return false;
            if (dyn.count(make_pair(pos, step)) == 0) {
                dyn[make_pair(pos, step)] = canCross(table, pos + step, step - 1, dest, dyn)
                                         || canCross(table, pos + step, step, dest, dyn)
                                         || canCross(table, pos + step, step + 1, dest, dyn);
            }
            return dyn[make_pair(pos, step)];
        }
    };

Log in to reply
 

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