Java solution using Dijkstra's algorithm with min-Heap


  • 0

    Please refer here for the algorithm.
    Basically, each node is a combination of (ring location, current key index), and edge is the distance between two nodes.

    public class Solution {
        class Edge {
            int idx, loc, len;
            Edge (int idx, int loc, int len) {
                this.idx=idx;
                this.loc=loc;
                this.len=len;
            }
        }
        class EdgeComp implements Comparator<Edge>{
            public int compare(Edge n1, Edge n2) {
                return n1.len -n2.len;
            }
        }
        private int distance(int from, int to, int len){
            int diff = Math.abs(from-to);
            return Math.min(diff, len-diff);
        }
        int helper(char[] ring, char[] key, Map<Character, List<Integer>> ringMap){
            PriorityQueue<Edge> heap = new PriorityQueue(new EdgeComp());
            Integer[][] nodes = new Integer[ring.length+1][key.length+1];
            boolean[][] visited = new boolean[ring.length+1][key.length+1];
            nodes[0][0] = 0;
            heap.offer(new Edge(0, 0, 0));
            int ret = Integer.MAX_VALUE;
            while (! heap.isEmpty()){
                Edge cur = heap.poll();
                if (! visited[cur.loc][cur.idx]) {
                    visited[cur.loc][cur.idx] = true;
                    if (cur.idx == key.length) {
                        return nodes[cur.loc][cur.idx];
                    }
                    for (int next: ringMap.get(key[cur.idx])) {
                        int dis = distance(cur.loc, next, ring.length)+1+nodes[cur.loc][cur.idx];
                        nodes[next][cur.idx+1] = nodes[next][cur.idx+1] == null? dis : Math.min( dis, nodes[next][cur.idx+1]);
                        heap.offer( new Edge(  cur.idx+1, next, dis) );
                    }
                }
            }
            return ret;
        }
        public int findRotateSteps(String ring, String key) {
            if (key==null || key.length()==0) return 0;
            Map<Character, List<Integer>> ringMap = new HashMap<>();
            char[] cc = ring.toCharArray();
            int ringLen = cc.length; 
            for (int i=0; i<ringLen; i++){
                char c = cc[i];
                ringMap.putIfAbsent(c, new ArrayList<Integer>());
                ringMap.get(c).add(i);
            }
            return helper(cc, key.toCharArray(), ringMap);
        }
    }
    

Log in to reply
 

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