752. Open the Lock

This problem is similar to 127. Word Ladder (My solution). Such problems can be taken as maze problem and be solved in bidirectional bfs.

The key steps are marked as comments in the following code:

public int openLock(String[] deadends, String target) {
    Set<String> deadSet = new HashSet<String>();
    for(int i = 0; i < deadends.length; i++)
        deadSet.add(deadends[i]);
	
    // Use set instead of queue to accelerate search
    Set<String> beginSet = new HashSet<String>();
    Set<String> endSet = new HashSet<String>();
    beginSet.add("0000");
    endSet.add(target);
    // Search from begin and end simultaneously
    return deadSet.contains("0000") || deadSet.contains(target) ? -1 : traverse(beginSet, endSet, deadSet);
}

public int traverse(Set<String> beginSet, Set<String> endSet, Set<String> deadSet) {
    Set<String> newSet = new HashSet<String>();
    for(String current: beginSet) {
        StringBuilder sb = new StringBuilder(current);
        for(int i = 0; i < 4; i++) {
            char originalChar = current.charAt(i);
            sb.setCharAt(i, (char)((originalChar - '0' + 1) % 10 + '0'));
            if( endSet.contains(sb.toString()) )
                return 1;
            if( !deadSet.contains(sb.toString()) ) {
                newSet.add(sb.toString());
                deadSet.add(sb.toString()); // the searched elements are taken as deadend
            }

            sb.setCharAt(i, (char)((originalChar - '0' + 9) % 10 + '0'));
            if( endSet.contains(sb.toString()) )
                return 1;
            if( !deadSet.contains(sb.toString())) {
                newSet.add(sb.toString());
                deadSet.add(sb.toString());
            }

            sb.setCharAt(i, originalChar);
        }
    }
    if( newSet.size() == 0 )
        return -1;
    beginSet = newSet;
    // Each time search from the set with less elements 
    int result = beginSet.size() > endSet.size() ? 
            traverse(endSet, beginSet, deadSet) : traverse(beginSet, endSet, deadSet);
    return result == -1 ? -1 : result + 1;
}