题解 | 密码锁 dfs也可以做 java 319ms

import java.util.*;

import java.io.*;

public class Main {
    public static void main(String[]args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int len = in.nextInt();
            String s = in.next();
            int[]list = new int[3];
            for (int i = 0; i < len; i++)
                list[s.charAt(i) - '0']++;
            if (list[0] > 0 && list[1] > 0 && list[2] > 1) {
                System.out.println(all(s));
            } else {
                System.out.println("-1");
            }
        }
    }

    public static int all(String s) {
        Map m = new HashMap<String, Integer>();
        int i = 0;
        for ( ; dfs(s, 0, i, m) == false; i++) {
            m.clear();
        };
        return i;
    }

    public static boolean dfs(String s, int k, int n, Map m) {
        if (m.containsKey(s)) {
            if ((int)m.get(s) > k) {
                m.put(s, k);
            } else {
                return false;
            }
        } else {
            m.put(s, k);
        }

        if (k > n) {
            return false;
        }
        for (int i = 0; i < s.length() - 3; i++) {
            if (s.substring(i, i + 4) .equals( "2012") ) {
                return true;
            }
        }
        for (int i = 0; i < s.length() - 1; i++) {
            char[] list = s.toCharArray();
            char c = list[i + 1];
            list[i + 1] = list[i];
            list[i] = c;
            String str = String.valueOf(list);
            if (dfs(str, k + 1, n, m)) {
                return true;
            };
        }
        return false;
    }
}