752. Open the Lock!

class Solution {
    public int openLock(String[] deadends, String target) {
        // BFS
        Set<String> invalids = new HashSet<>();
        for(String str: deadends){
            invalids.add(str);
        }
        
        Queue<String> queue = new LinkedList<>();
        
        // corner case
        if(invalids.contains("0000")) return -1;
        queue.offer("0000");
        
        int step=0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-->0){
                String curr = queue.poll();
                if(curr.equals(target)) return step;

                for(int i=0; i<4; i++){
                    String up = up(curr, i);
                    String down = down(curr, i);
                    if(!invalids.contains(up)){
                        queue.offer(up);
                        invalids.add(up);
                    }
                    if(!invalids.contains(down)){
                        queue.offer(down);
                        invalids.add(down);
                    }
                } 
            }

            step++;
        }
        return -1;
    }
    
    private String up(String s, int index){
        char[] chars =s.toCharArray();
        if(chars[index]=='9') chars[index] = '0';
        else chars[index]++;
        return new String(chars);
    }
    
    private String down(String s, int index){
        char[] chars = s.toCharArray();
        if(chars[index]=='0') chars[index] = '9';
        else chars[index]--;
        return new String(chars);
    }
}