# JAVA clear and simple BFS solution

• Not super smart but straightforward.
To pass the OJ, we have to prune the branches that are obviously too long.

``````    class Status{
int steps = 0, pos = 0;
Status(int steps, int pos){
this.steps = steps;
this.pos = pos;
}
}
public int findRotateSteps(String ring, String key) {
int n = ring.length();
HashMap<Character, HashSet<Integer>> map = new HashMap<Character, HashSet<Integer>>();
int [][] gaps = new int[n][n];
for (int i=0;i<n;i++)
for (int j=i;j<n;j++)
gaps[i][j] = gaps[j][i] = Math.min(j-i, i+n-j);
for (int i=0;i<ring.length();i++){
HashSet<Integer> t;
if (map.containsKey(ring.charAt(i)))
t = map.get(ring.charAt(i));
else
t = new HashSet<Integer>();
map.put(ring.charAt(i),t);
}
ArrayDeque<Status> q = new ArrayDeque<Status>();
Status s = new Status(0,0);
int min = 0;
int minPos = 0;
for (int i=0;i<key.length();i++){
int l = q.size();
int newMin = Integer.MAX_VALUE;
int newPos = 0;
boolean isAna = false;
for (int j=0;j<l;j++){
s = q.pollFirst();
int step = gaps[minPos][s.pos];
if (s.steps>min && s.steps-min>=step)
continue;
for (int p:map.get(key.charAt(i))){
step = gaps[p][s.pos] + s.steps + 1;
if (step<newMin){
newMin = step;
newPos = p;
}
else{
int tstep = gaps[newPos][p];
if (step-newMin>=tstep)
continue;
}
Status s1 = new Status(step, p);