complicated solution


  • 0
    W
    public:
    
        //it2 is one behind the last
        bool canJumphelper(vector<int>&nums,vector<int>::iterator it1,vector<int>::iterator it2,unordered_map<int,int>& map){
            
            if(it1 == it2-1){
                return true;
            }
            int dis = distance(it1,it2);
            bool cando = 0;
            for(int i=1;i < dis;i++){
                //we want the key of map to be the position, and value to be if it is true
                if(map[int(it2-i-1-it1)]==1){
                    break;
                }
                if(*(it2-i-1)>=i){
                    if (canJumphelper(nums,it1,it2-i,map) == true){
                        return true;
                    }
                }
                map[int(it2-i-1-it1)] = 1;
                
            }
            return cando;
            
        }
        
        bool canJump(vector<int>& nums) {
            unordered_map<int,int> map;
            return canJumphelper(nums, nums.begin(),nums.end(),map);
            
        }
    };
    

Log in to reply
 

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