*Java* 7ms divide and conquer method


  • 0
    E

    Using memoization does not help at all for this problem. One possible reason might be that the strings in the test cases are all short. Any comment?

    public class Solution {
    
    public List<Integer> diffWaysToCompute(String input) {
        List<Character> operations = new ArrayList<Character>();
        List<Integer> nums = new ArrayList<Integer>();
        int number = 0;
        for(int i=0, L=input.length(); i<L; i++) {
        	char ch = input.charAt(i);
        	if(!(ch-'0'<=9 && ch-'0'>=0)) {
        		nums.add(number);
        		operations.add(ch);
        		number = 0;
        	}
        	else {
        		number = number*10 + (ch-'0');
        	}
        }
        nums.add(number);
        HashMap<int[], List<Integer>> map = new HashMap<int[], List<Integer>>();
        return diffWaysToCompute(map, nums, operations, 0, nums.size()-1);
    }
    
    private List<Integer> diffWaysToCompute(HashMap<int[], List<Integer>> map, List<Integer> nums, List<Character> operations, int start, int end) {
    	//if(map.containsKey(new int[]{start, end})) return map.get(new int[]{start, end});
    	List<Integer> list = new LinkedList<Integer>();
    	if(start==end) {
    		list.add(nums.get(start));
    		return list;
    	}
    	for(int i=start; i<end; i++) {
    		List<Integer> leftRes = diffWaysToCompute(map, nums, operations, start, i);
    		List<Integer> rightRes = diffWaysToCompute(map, nums, operations, i+1, end);
    		for(int left : leftRes) {
    			for(int right : rightRes) {
    				switch(operations.get(i)) {
    					case '+': list.add(left+right); break;
    					case '-': list.add(left-right); break;
    					case '*': list.add(left*right); break;
    				}
    			}
    		}
    	}
    	//map.put(new int[]{start, end}, list);
    	return list;
    }
    }

  • 0
    M

    Tried the following and the running time is half comparing to int[] keys.

    HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    
    if (map.containsKey(start * nums.size() + end)) {
        return map.get(start * nums.size() + end);
    }
    
    map.put(start * nums.size() + end, list);
    

Log in to reply
 

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