Not Simple but Universal using graph and shortest path


  • 0
    Q
        public int minMutation(String start, String end, String[] bank) {
            if (start.equals(end)) return 0;
            int n = bank.length;
            boolean[][] isMuted = new boolean[n + 1][n + 1];
            int endPos = -1;
            for (int i = 0; i < n; i++) {
                if (bank[i].equals(end)) endPos = i;
                isMuted[i][n] = isOk(start, bank[i]);
                isMuted[n][i] = isMuted[i][n];
                for (int j = i + 1; j < n; j++) {
                    isMuted[i][j] = isOk(bank[i], bank[j]);
                    isMuted[j][i] = isMuted[i][j];
                }
            }
            if (endPos < 0) return -1;
            Set<Integer> usedSet = new HashSet<>();
            usedSet.add(n);
            return helper(isMuted, n, endPos, usedSet);
        }
    
        public boolean isOk(String a, String b) {
            if (a.length() != b.length()) return false;
            int cnt = 0;
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) cnt++;
                if (cnt > 1) return false;
            }
            return cnt == 1;
        }
    
        public int helper(boolean[][] isMuted, int pos, int end, Set<Integer> set) {
            int min = Integer.MAX_VALUE;
            boolean find = false;
            for (int i = 0; i < isMuted.length; i++) {
                if (!set.contains(i) && isMuted[pos][i]) {
                    if (i == end) return 1;
                    set.add(i);
                    int tmp = helper(isMuted, i, end, set);
                    if (tmp > 0) find = true;
                    if (tmp > 0 && tmp < min) min = tmp;
                    set.remove(i);
                }
            }
            return !find ? -1 : (min == -1 ? -1 : 1 + min);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.