Open the Lock

Java

public class Solution {
    /**
     * @param deadends: the list of deadends
     * @param target: the value of the wheels that will unlock the lock
     * @return: the minimum total number of turns 
     */
	public int openLock(String[] deadends, String target) {
		
		String start = "0000";
		Set<String> deadSet = new HashSet<>();
		
		for (String str : deadends) {
			if (str.equals(start)) {
				return -1;
			}
			deadSet.add(str);
		}
		
		int result = 0;
		Queue<String> queue = new LinkedList<>();
		Set<String> set = new HashSet<>();
		
		queue.offer(start);
		set.add(start);
	
		while (!queue.isEmpty()) {
			int n = queue.size();
			
			for (int i = 0; i < n; i++) {
				String cur = queue.poll();
				if (cur.equals(target)) return result;
				for (String next : getNextCur(cur, deadSet, set)) {
					if (!set.contains(next)) {
					queue.offer(next);
					set.add(next);
				}
	
				}
			}
			result += 1;
		}
		return -1;
}
//char int string 之间相互转化的一些套路
private List<String> getNextCur(String cur, Set<String> deadSet, Set<String> set) {
		List<String> nextCurs = new ArrayList<>();
		for (int i = 0; i < 4; i++) {  // 四个锁
			char[] chars = cur.toCharArray();
			char origin = chars[i];
			
			chars[i] = (char)((origin - '0' + 1) % 10 + '0');  //+1操作
			String next = new String(chars);
			
			if (!deadSet.contains(next) && !set.contains(next)) {
					nextCurs.add(next);
			}
			
			chars[i] = (char)((origin - '0' - 1 + 10) % 10 + '0'); //-1操作
			next = new String(chars);
			
			if (!deadSet.contains(next) && !set.contains(next)) {
					nextCurs.add(next);
			}
			}
			return nextCurs;
		}
}