# AC JAVA Solution using 2-end BFS

• Each time we work with a smaller-sized set by checking the set from "0000" end and from target end (to save time).
At any instance, if either set is empty, it means we hit a dead end. So return -1.
If we match a password from the other end, we find the solution. So return counter at that moment.
Note: if you have encountered the 38/40 wrong answer problem, just check whether "0000" is in your deadends. This should solve the problem.

``````class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dds = new HashSet<>();
if (dds.contains("0000")) return -1;
Set<String> start = new HashSet<>();
Set<String> end = new HashSet<>();
Set<String> visited = new HashSet<>();
int counter = 0;
while (!start.isEmpty() && !end.isEmpty()) {
counter++;
if (start.size() > end.size()) {
Set<String> temp = start;
start = end;
end = temp;
}
Set<String> temp_start = new HashSet<>();
for (String s : start) {
for (int i = 0; i < 4; i++) {
char[] s1_arr = s.toCharArray();
char[] s2_arr = s.toCharArray();
s1_arr[i]++;
s2_arr[i]--;
if (s1_arr[i] > '9') s1_arr[i] -= 10;
if (s2_arr[i] < '0') s2_arr[i] += 10;
String s1 = String.valueOf(s1_arr);
String s2 = String.valueOf(s2_arr);
if (end.contains(s1) || end.contains(s2)) return counter;
if (!dds.contains(s1) && !visited.contains(s1)) {
}
if (!dds.contains(s2) && !visited.contains(s2)) {