752 open the lock

https://leetcode.com/problems/open-the-lock/

class Solution {
    public int openLock(String[] dde, String target) {
        Set<String> deadends = new HashSet<>();
        for (String deadend : dde) {
            deadends.add(deadend);
        }
        if (deadends.contains(target) || deadends.contains("0000")) return -1;
        int steps = 0;
        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                String lock = queue.poll();
                // System.out.println(lock);
                if (lock.equals(target)) {
                    return steps;
                }
                if (visited.contains(lock)) {
                    continue;
                }
                visited.add(lock);
                char[] state = lock.toCharArray();
                for (int i = 0; i < state.length; i++) {
                    char nextCh;
                    char preCh;
                    if (state[i] == '0') {
                        nextCh = '1';
                        preCh = '9';
                    } else if (state[i] == '9') {
                        nextCh = '0';
                        preCh = '8';
                    } else {
                        nextCh = (char)(state[i] + 1);
                        preCh = (char)(state[i] - 1);
                    }
                    char tmp = state[i];
                    state[i] = nextCh;
                    String nextLock = new String(state);
                    state[i] = preCh;
                    String preLock = new String(state);
                    //记得还回去，i还会往下一格wheel移动
                    state[i] = tmp;
                    if (!deadends.contains(nextLock)) {
                        queue.offer(nextLock);
                    }
                    if (!deadends.contains(preLock)) {
                        queue.offer(preLock);
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

两点要注意的，第一是deadend是可能被绕开的，因此每次要往两个方向转动轮子，第二是每次四个轮子都要尝试，试完上一个记得重置state，因为四次都是在state上修改的