752. Open the Lock

別忘了 visited

T: O(10^4 + deadsize), 在 10^4 上搜索
S: O(deadends.length)

class Solution {
    public int openLock(String[] deadends, String target) {
        
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));

        if (dead.contains("0000")) {
            return -1;
        }
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        visited.add("0000");
            
        int turns = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                String cur = queue.poll();
                
                if (target.equals(cur)) {
                    return turns;
                }
                // so 4*2 種
                for (int i = 0; i < 4; i++) {
                    for (int roll = -1; roll <= 1; roll += 2) { // roll 1 or -1
                                     
                        String str = cur;
                        char[] curArray = cur.toCharArray();
                        
                        int num = cur.charAt(i) - '0';    
                        curArray[i] = (char)((num + 10 + roll) % 10 + '0'); // because 0 - 1 )%10 = -1, so add 10
                        
                        String next = String.valueOf(curArray);
                        if (dead.contains(next)) {
                            continue;
                        }
                        if (visited.contains(next)) {
                            continue;
                        }
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
            turns++;
        }
        return -1;
    }
}

/*
a list of deadends dead ends, can't open

return the minimum total number of turns required to open the lock, or -1 if it is impossible.

bfs

add deadends to hashset<String>


0000 use 4 digit add one

if not in hashset<String>



0000
0100
0200
0201  
0202  =>4


T: O(10^4 + deadsize), 在 10^4 上搜索
S: O(deadends.length)


但可以往前也可以往後撥, 所以如果是 0 -> 1 已可以 0->9
*/

new version

Ｔ：Ｏ（4*10^4 + deads to Set) 
4 is for loop, 10 (0~9), 4 digits combination, so 4*10*4

S: O(10^4(queue) + visited + deads to Set)

class Solution {
    private String up(String s, int position) {
        char[] c = s.toCharArray();
        if (c[position] == '9') {
            c[position] = '0';
        } else {
            c[position]++;
        }
        return String.valueOf(c);
    }
    private String down(String s, int position) {
        char[] c = s.toCharArray();
        if (c[position] == '0') {
            c[position] = '9';
        } else {
            c[position]--;
        }
        return String.valueOf(c);
    }
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        visited.add("0000");
        
        int turns = 0;
        while (!queue.isEmpty()) {
            int size = queue.size(); // 別忘了這個要提出來..queue size 是會變的
            for (int q = 0; q < size; q++) {
                String cur = queue.poll();
                if (dead.contains(cur)) {
                    continue;
                }
                if (target.equals(cur)) {
                    return turns;
                }
                for (int i = 0; i < 4; i++) {
                    String up = up(cur, i);
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    
                    String down = down(cur, i);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            turns++;
        }
        return -1;
    }
}

/*
start from "0000" ->

up or down, if not 0, 9, up : -1, down: +1
'9' to be '0', or '0' to be '9'

use bfs to find how many turns to arive "target"

Ｔ：Ｏ（4*10^4 + deads to Set) 
4 is for loop, 10 (0~9), 4 digits combination, so 4*10*4

S: O(10^4(queue) + visited + deads to Set)
*/