Fast Recursive Java Solution


  • 0
    J

    Base solution is here. We declare the recurrence:

    Recurrence:
    canCross(pos, speed) = 
    canCross(pos+speed, speed) || 
    speed > 1 && canCross(pos+speed-1, speed-1) || 
    canCross(pos+speed+1, speed+1)
    
    Base case:
    1. canCross(pos=stones[LastIndex], ?) = true
    2. canCross(pos>stones[LastIndex], ?) = false
    
    public class Solution {
        private boolean canCross(Set<Integer> s, int end, int curr, int speed) {
            if(curr >= end) {
                return curr == end;
            }    
            
            return s.contains(curr+speed) && canCross(s, end, curr+speed, speed) ||
                s.contains(curr+speed+1) && canCross(s, end, curr+speed+1, speed+1) ||
                speed > 1 && s.contains(curr+speed-1) && canCross(s, end, curr+speed-1, speed-1);
        }
        
        public boolean canCross(int[] stones) {
            Set<Integer> s = new HashSet<>();
            for(int n : stones) {
                s.add(n);
            }
            
            if(s.contains(stones[0] + 1)) {
                return canCross(s, stones[stones.length-1], stones[0] + 1, 1);
            } else {
                return false;
            }
        }
    }
    

    If you submit the above code, you get TLE.
    Now it is time to optimize your algorithm with cache.

    Why we need a cache? Because the recursion will produce duplicate subproblem.

    public class Solution {
        private String ck(int a, int b) {
            return String.valueOf(a) + "@" + String.valueOf(b);
        }
        
        private boolean canCross(Set<Integer> s, int end, int curr, int speed, Map<String, Boolean> cache) {
            if(curr >= end) {
                return curr == end;
            }    
            
            String key = ck(curr, speed);
            Boolean val = cache.get(key); 
            if(val != null) {
                return val.booleanValue();
            }
            
            boolean flag = s.contains(curr+speed) && canCross(s, end, curr+speed, speed, cache) ||
                s.contains(curr+speed+1) && canCross(s, end, curr+speed+1, speed+1, cache) ||
                speed > 1 && s.contains(curr+speed-1) && canCross(s, end, curr+speed-1, speed-1, cache);
                
            cache.put(key, flag);
            return flag;
        }
        
        public boolean canCross(int[] stones) {
            Set<Integer> s = new HashSet<>();
            for(int n : stones) {
                s.add(n);
            }
            
            if(s.contains(stones[0] + 1)) {
                return canCross(s, stones[stones.length-1], stones[0] + 1, 1, new HashMap<String, Boolean>());
            } else {
                return false;
            }
        }
    }
    

Log in to reply
 

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