Super simple solution, dfs with memorization


  • 0

    The idea is too simple, or sometimes naive.
    Calculate the distance between each stone and compare if it matches (step - 1), step, or (step + 1).
    If a match is found, dfs it. If a solution is found, return. If a failure found, record it so other routes dfs can avoid retrying the same work.

    Time consumption is reasonable, beat 70%.

    class Solution {
        public boolean canCross(int[] stones) {
            if (stones == null || stones.length < 2) return false;
            if (stones[1] != 1) return false;
            return dfs(stones, 1, 1, new HashSet<String>());
        }
        
        private boolean dfs(int[] stones, int start, int step, Set<String> set) {
            if (start == stones.length - 1) {
                return true;
            }
            if (set.contains(start + "-" + step)) return false; // Failare doomed
            for (int i = start + 1; i < stones.length; i++) {
                int delta = stones[i] - stones[start];
    
                if (delta > step + 1) break;
                if (delta == step - 1) {
                    if (dfs(stones, i, step - 1, set)) return true;
                } else if (delta == step) {
                    if (dfs(stones, i, step, set)) return true;
                } else if (delta == step + 1) {
                    if (dfs(stones, i, step + 1, set)) return true;
                }
            }
            // Add the case for record
            set.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.