Java Special DP Solution Beats 100%


  • 0
    Q

    Using traditional array DP approach will cost lots of time. Better to use linked list to implement DP problem with small number of sub-problems.

    public class Solution {
        public static class DP {
    		int place; //current place in this sub-problem
    		int counter; //current steps in this sub-problem
    		DP(int x, int y) {
    			place = x;
    			counter = y;
    		}
    	}
    	public static int findRotateSteps(String ring, String key) {
            List<Integer>[] dict = new List[26];
            char[] ringarray = ring.toCharArray();
            for(int i = 0; i < ringarray.length; i++) {
            	if(dict[ringarray[i] - 'a'] == null) {
            		List<Integer> tmp = new ArrayList();
            		tmp.add(i);
            		dict[ringarray[i] - 'a'] = tmp;
            	}
            	else {
            		dict[ringarray[i] - 'a'].add(i);
            	}
            }
            char[] keyarray = key.toCharArray();
            List<DP> hash = new LinkedList();
            hash.add(new DP(0, 0));
            int len = ringarray.length;
            for(char c : keyarray) {
            	List<DP> tmp = new LinkedList();
            	for(int place : dict[c - 'a']) {
            		int min = Integer.MAX_VALUE;
            		for(DP d : hash) {
            			int diff = Math.abs(d.place - place);
            			int step = Math.min(d.counter + diff, d.counter + len - diff);
            			if(step < min) min = step + 1; 
            		}
            		tmp.add(new DP(place, min));
            	}
            	hash = tmp;
            }
            int answer = Integer.MAX_VALUE;
            for(DP f : hash) {
            	if(f.counter < answer) answer = f.counter;
            }
            return answer;
        }
    }
    

Log in to reply
 

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