403. Frog Jump

Version #3 HashMap of stones and Keep recording the failed tries
Give the k of last step, we know now we can only jump k-1, k, k+1
current position x + k-1/k/k+1 is not a valid stone position, then no need to explore
Pruning -> given a position x, if we have tried that there's no way for us to read the end given a k, then next time we come to x again, we know that we don't need to explore x with a k again
So I maintained a Map<Integer, Set<Integer>> whose key is position x, and value is set of invalid k

Time O(3^step) ??
Space O(nk) ??

79.15 %
class Solution {
    public boolean canCross(int[] stones) {
Set<Integer> stoneSet = new HashSet<>();
Map<Integer, Set<Integer>> failMap = new HashMap<>();
for (int stone : stones) {
stoneSet.add(stone);
failMap.put(stone, new HashSet<>());
}
if (!stoneSet.contains(1)) {
return false;
}
return dfs(failMap, stoneSet, 1, 1, stones[stones.length - 1]);
}

private boolean dfs(Map<Integer, Set<Integer>> failMap, Set<Integer> stoneSet, int x, int k, int target) {
if (x >= target) {
return true;
}
for (int nextK = k - 1; nextK <= k + 1; nextK++) {
if (nextK > 0 && stoneSet.contains(x + nextK)) {
if (!failMap.get(x).contains(nextK) && dfs(failMap, stoneSet, x + nextK, nextK, target)) {
return true;
} else {
failMap.get(x).add(nextK);
}
}
}
return false;
}
}


Version #2 HashMap of steps
二刷
感觉问题很直观，之前的Version#1思路挺有意思的，回头再看看
给每一个石头的position维护一个以position为key，能够往前走的steps set 为value的hashmap
每次走到一个石头，遍历它的set，如果从当前pos + k 能走到另外一个石头（hashmap contains key），那么就在能走到的那个石头的set里面加上k, k - 1, k + 1
如果pos + k恰好等于最后一块石头的pos，就直接返回true

一个bug是一直有 concurrent exception
问题大概出在对于set同时遍历又同时add
本来以为要一个iterator
后来发现在代码里加上 if (k > 1) {  set.add(k - 1) } 的限制条件就行了
这样保证正在iterate 的set 和之后add的set不会是同一个set
又仔细想了想，这个问题主要是针对 j = 0 (pos = 0) 和j = 1 (pos = 1)的时候两个edge case
走0步的时候会同时编辑正在iterate的set
62.82 %

class Solution {
    public boolean canCross(int[] stones) {
        if (stones == null || stones.length == 0) return false;
        if (stones.length == 1) return true;
        if (stones[1] > 1) return false;
        // key-stone position, value-set of possible steps
        Map<Integer, Set<Integer>> steps = new HashMap<>();
        int length = stones.length;
        for (int i = 0; i < length; i++) {
            steps.put(stones[i], new HashSet<>());
        }
        steps.get(0).add(1);
        Set<Integer> currKSet = null;
        Set<Integer> nextKSet = null;
        for (int j = 0; j < length - 1; j++) {
            for (int k : steps.get(stones[j])) {
                int next = stones[j] + k;
                if (next == stones[length - 1]) return true;
             
                nextKSet = steps.get(next);
                if (nextKSet != null) {
                    if (k > 1) {
                        nextKSet.add(k - 1);
                    }
                    nextKSet.add(k);
                    nextKSet.add(k + 1);
                }
            }
        }
        return false;
    }
}


Version #1
一个时间复杂度稍微有点高的方法，每次从position开始向后看所有的stones，如果小于dist就继续向后看，如果大于dist就break
这样当k很大的时候，相当于做了很多无用的搜索
优化方法是维护一个hashmap key是dist from start point，value是index
这样可以直接搜索出距离当前position 的距离为k-1, k, k+1的stone是否存在
优化有空再写

关键是要用memorization进行pruning，否则会TLE
因为这里对于每一个stone，k是不连续的，所以此处要对k用hashmap

所以是一个list of hashmap，每一个stone里面有一个相应的以k为key，canCross为value的hashmap
80.22 %
public class Solution {
    public boolean canCross(int[] stones) {
        if (stones == null) throw new IllegalArgumentException();
        if (stones.length <= 1) return true;
        //must jump 1 step
        if (stones[1] > 1) return false;
     
        //for every stone, there's a hash map
        //key-k(last step), value-canCross
        List<Map<Integer, Boolean>> visited = new ArrayList<>();
        for (int i = 0; i < stones.length; i++) {
            visited.add(new HashMap<Integer, Boolean>());
        }
     
        //Standing at the first stone && had jumped 1 step
        return canCross(stones, 1, 1, visited);
    }
    //Standing at each position, the frog can jump to the stone in k-1/k/k+1 units, k is the jumpint distance of the last step
    private boolean canCross(int[] stones, int position, int k, List<Map<Integer, Boolean>> visited) {
        Map<Integer, Boolean> visitedMap = visited.get(position);
        if (visitedMap.containsKey(k)) return visitedMap.get(k);
     
     
        if (position == stones.length - 1) return true;
        for (int nextPosition = position + 1; nextPosition < stones.length; nextPosition++) {
            int dist = stones[nextPosition] - stones[position];
            if (dist < k - 1) continue;
            if (dist > k + 1) break;
            //k-1 <= dist <= k+1
            if (canCross(stones, nextPosition, dist, visited)) {
                visitedMap.put(k, true);
                return true;
            }
        }
        visitedMap.put(k, false);
        return false;
    }
}