# Java solution using Dijkstra's algorithm with min-Heap

• 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>());