752. Open the Lock

二刷 07/2022

Version #1 BFS level order traversal

犯了一个错误就是每次只有一个bit可以rotate，我想成每次4个bits都可以freely地变成上一个或者下一个，然后傻了吧唧的写了一个dfs来generate next code

另外一个错误就是deadend有可能包含init state，我只讨论了target等于init state的请况却漏了deadend包含init state的情况

还有一个就是char虽然可以直接做加减法，但是做完加减法之后会变成int，然后再赋值给char就会报loss of accuracy的错，必须explicitly cast成char才行

Time O(4^2 * 10^4) - 如果4是N的话getNextCode这个function是O(N^2)的复杂度，因为iterate了N个digit然后每个digit又O(N)的时间计算String.valueOf(chars)

• Time Complexity: $O(N^2 * \mathcal{A}^N + D)$ where $\mathcal{A}$ is the number of digits in our alphabet, $N$ is the number of digits in the lock, and $D$ is the size of deadends. We might visit every lock combination, plus we need to instantiate our set dead. When we visit every lock combination, we spend $O(N^2)$ time enumerating through and constructing each node.

• Space Complexity: $O(\mathcal{A}^N + D)$, for the queue and the set dead.

Runtime: 118 ms, faster than 83.49% of Java online submissions for Open the Lock.

Memory Usage: 71.1 MB, less than 72.54% of Java online submissions for Open the Lock.

class Solution {

    public int openLock(String[] deadends, String target) {

        String init = "0000";

        if (init.equals(target)) {

            return 0;

        }

        Set<String> deadendSet = new HashSet<>();

        for (String deadend : deadends) {

            deadendSet.add(deadend);

        }

        if (deadendSet.contains(init)) {

            return -1;

        }

        Set<String> visited = new HashSet<>();

        Queue<String> que = new ArrayDeque<>();

        visited.add(init);

        que.offer(init);

        int step = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            step++;

            while (size-- > 0) {

                String curr = que.poll();

                for (String next : getNextCode(curr)) {

                    if (deadendSet.contains(next) || visited.contains(next)) {

                       continue;

                    }

                    if (next.equals(target)) {

                        return step;

                    }

                    visited.add(next);

                    que.offer(next);

                }

            }

        }

        return -1;

    }

    

    private List<String> getNextCode(String curr) {

        char[] chars = curr.toCharArray();

        List<String> codes = new ArrayList<>();

        // only 1 bit can be rotated

        for (int i = 0; i < chars.length; i++) {

            char c = chars[i];

            chars[i] = c == '0' ? '9' : (char)(c - 1);

            codes.add(String.valueOf(chars));

            chars[i] = c == '9' ? '0' : (char)(c + 1);

            codes.add(String.valueOf(chars));

            chars[i] = c;

        }

        return codes;

    }

}

一刷
Classical BFS


76.45 %
// increment i = (i + 1) % 10
// decrement i = (i + 9) % 10

class Solution {
    public int openLock(String[] deadends, String target) {
String init = "0000";
Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        if (visited.contains(init)) {
            return -1;
        }
Queue<String> que = new LinkedList<>();
que.offer(init);
int step = 0;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
String curr = que.poll();
if (curr.equals(target)) {
return step;
}
char[] chars = curr.toCharArray();
for (int i = 0; i < 4; i++) {
// increment
char c = chars[i];
chars[i] = (char)('0' + ((c - '0' + 1) % 10));
String next = new String(chars);
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
                    // decrement
chars[i] = (char)('0' + ((c - '0' + 9) % 10));
next = new String(chars);
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
chars[i] = c;
}
}
step++;
}
return -1;
}
}