622. Frog Jump

Code(Language:C++)

class Solution {
public:
    /**
     * @param stones: a list of stones' positions in sorted ascending order
     * @return: true if the frog is able to cross the river or false
     */
    bool canCross(vector<int> &stones) {
        // write your code here
        const int size = stones.size();
        if(size <= 1){
            return true; 
        }
        if(stones[0] + 1 != stones[1]){
            return false; 
        }
        unordered_map<int, unordered_set<int>> mp;
        for(auto i : stones){
            mp[i] = unordered_set<int>(); 
        }
        mp[stones[1]].insert(1);
        for(int i = 1; i < size; i++){
            int pos = stones[i];
            for(auto k : mp[pos]){
                if(k - 1 > 0){
                    if(mp.count(pos + k - 1)){
                        mp[pos + k - 1].insert(k - 1); 
                    }
                }
                if(mp.count(pos + k)){
                    mp[pos + k].insert(k); 
                }
                if(mp.count(pos + k + 1)){
                    mp[pos + k + 1].insert(k + 1); 
                }
            }
        }
        return mp[stones[size - 1]].size() > 0; 
    }
};