beats 86.12% of java submissions. Memorized DFS Solution.


  • 0
    T
    public class Solution {
        
        Map<Integer, Integer> map;
        int n;
        Set<String> visited;
        
        public boolean canCross(int[] stones) {
            
            
            map =new HashMap<>();
            n = stones.length;
            visited = new HashSet<>();
            
            if(n>=1 && stones[1]!=1)
                return false;
            
                
            for(int i=0; i<n; i++)
                map.put(stones[i], i);
            
            return dfs(stones, 1, 1);
        }
        
        public boolean dfs(int[] stones, int start, int step){
            
        	if(visited.contains(start+" "+step))
        	    return false;
        	   
            if(start>=n-1)
                return start==n-1;
            
            if(step-1>0 && map.containsKey(stones[start]+step-1) && dfs(stones, map.get(stones[start]+step-1), step-1))
                return true;
            
            if(map.containsKey(stones[start]+step) && dfs(stones, map.get(stones[start]+step), step))
                return true;
            if(map.containsKey(stones[start]+step+1) && dfs(stones, map.get(stones[start]+step+1), step+1))
                return true;        
            
            visited.add(start+" "+step);
            return false;
        }
    }
    

Log in to reply
 

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