你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每個撥輪可以自由旋轉：例如把 ‘9’ 變為 ‘0’，‘0’ 變為 ‘9’ 。每次旋轉都只能旋轉一個撥輪的一位數字。

鎖的初始數字為 ‘0000’ ，一個代表四個撥輪的數字的字符串。

列表 deadends 包含了一組死亡數字，一旦撥輪的數字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉。

字符串 target 代表可以解鎖的數字，你需要給出最小的旋轉次數，如果無論如何不能解鎖，返回 -1。

示例 1:

輸入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
輸出：6
解釋：
可能的移動序列為 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 這樣的序列是不能解鎖的，
因為當撥動到 “0102” 時這個鎖就會被鎖定。

代碼

class Solution {public int openLock(String[] deadends, String target) {StringBuilder stringBuilder=new StringBuilder();HashSet<String> hashSet=new HashSet<>();for(String s:deadends) hashSet.add(s);if(hashSet.contains("0000")) return -1;//起點就鎖住了Queue<String> queue=new LinkedList<>();queue.add("0000");HashSet<String> check=new HashSet<>();//記錄以及訪問過的字符串check.add("0000");int res=0;while (!queue.isEmpty()){int size=queue.size();for(int j=0;j<size;j++){String cur=queue.poll();for(int i=0;i<4;i++)//4個位置變化{stringBuilder=new StringBuilder(cur);char na=(char)(stringBuilder.charAt(i)+1),ns=(char)(stringBuilder.charAt(i)-1);//當前位置加一或減一if(na>'9') na='0'; else if(ns<'0') ns='9';stringBuilder.setCharAt(i,na);String temp=stringBuilder.toString();if(temp.equals(target)) return res+1;//找到了目標if(!hashSet.contains(temp)&&!check.contains(temp))//看看當前字符串有沒有被鎖或者被訪問過了{queue.offer(temp);check.add(temp);}stringBuilder.setCharAt(i,ns);temp=stringBuilder.toString();if(temp.equals(target)) return res+1;if(!hashSet.contains(temp)&&!check.contains(temp)){queue.offer(temp);check.add(temp);}}}res++;}return -1;}
}