beats 86.12% of java submissions. Memorized DFS Solution.

  • 0
    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;
                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.