5-line solution to record set of last steps to land on each stone


  • 0

    Solution inspired by @soamaaazing , simply to collect all possible last jumps to each stone, might not be efficient but very concise and straightforward.

        bool canCross(vector<int>& s) {
            // steps[pos] = set of last steps to land on position 'pos'
            unordered_map<int, unordered_set<int>> steps = {{0, {0}}};
            for (int pos : s)
                for (int x : steps[pos])
                    for (int i = max(1, x-1); i < x+2; ++i) steps[pos+i].insert(i);
            return !steps[s.back()].empty();
        }
    

Log in to reply
 

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