This is the 25th day of my participation in the genwen Challenge

The title

You have a turntable lock with four round paddles. Each dial wheel has 10 Numbers: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each dial wheel can rotate freely: for example, ‘9’ becomes ‘0’ and ‘0’ becomes ‘9’. Each rotation can only rotate one digit of one dial wheel.

The initial lock number is ‘0000’, a string representing the numbers of the four dial wheels.

The list deadends contains a set of death numbers. Once the number of the dial wheel matches any element in the list, the lock is permanently locked and cannot be rotated.

The string target represents the number that can be unlocked. You need to give the minimum number of rotations required to unlock it. If you can’t unlock it anyway, return -1.

 

  • Example 1:

Input: deadends = [“0201″,”0101″,”0102″,”1212″,”2002”], target = “0202” Could move the sequence of “0000” – > “1000” – > “1100” – > “1200” – > “1201” – > “1202” – > “0202”. Note that sequences such as “0000” -> “0001” -> “0002” -> “0102” -> “0202” cannot be unlocked because the lock will be locked when “0102” is tapped.

  • Example 2:

Deadends = [“8888”], target = “0009” Output: 1

  • Example 3:

Input: Deadends = [“8887″,”8889″,”8878″,”8898″,”8788″,”8988″,”7888″,”9888”], target = “8888” Output: -1 Description: Cannot rotate to target number and is not locked.

  • Example 4:

Input: deadends = [“0000”], target = “8888

Tip:

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • Target is not in deadends
  • Target and deadends[I] consist of only a few digits

Their thinking

  • Use queues for breadth-first search
  • Each change of position, or one operation, produces several strings, such as 0000, a change of one bit produces eight strings, such as 1000,0100,0010,0001,9000,0900,0090,0009, and so on
  • A string in deadends or traversed is not enqueued for breadth-first search

code

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++) { 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; }}Copy the code