JAVA clear and simple BFS solution


  • 0
    J

    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>();
                t.add(i);
                map.put(ring.charAt(i),t);
            }
            ArrayDeque<Status> q = new ArrayDeque<Status>();
            Status s = new Status(0,0);
            q.add(s);
            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);
                        q.addLast(s1);
                    }
                }
                min = newMin;
                minPos = newPos;
            }
            return min;
        }
    

Log in to reply
 

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