6 ms java recursive solution (parsing first, then calculate)


  • 0
    L
    public List<Integer> diffWaysToCompute(String input) {
            List<Character> ops = new ArrayList<Character>();
            List<Integer> nums = new ArrayList<Integer>();
            int val = -1;
            for (int i = 0; i < input.length(); i++) {
            	char c = input.charAt(i);
            	if (c == '+' || c == '-' || c == '*') {
            		if (val >= 0) {
            			nums.add(val);
            			val = -1;
            		}
            		ops.add(c);
            	}
            	else {
            		if (val < 0) val = c - '0';
            		else val = val * 10 + c - '0';
            	}
            }
            if (val >= 0) nums.add(val);
            
            return calculate(ops, nums, 0, nums.size() - 1);
        }
        
        List<Integer> calculate(List<Character> ops, List<Integer> nums, int si, int ei){
        	List<Integer> res = new ArrayList<Integer> ();
        	if (si == ei) res.add(nums.get(si));
        	else if (ei - si == 1) res.add(getValue(nums.get(si), nums.get(ei), ops.get(si)));
        	else {
        		for (int i = si; i < ei; i++)
        		{
        			List<Integer> left = calculate(ops, nums, si, i);
        			List<Integer> right = calculate(ops, nums, i+1, ei);
        			for (int v1 : left)
        				for (int v2 : right) {
        					res.add(getValue(v1, v2, ops.get(i)));
        				}
        		}
        	}
        	return res;
        }
        
        int getValue(int a, int b, char op) {
        	if (op == '+') return a + b;
        	else if (op == '-') return a - b;
        	else return a * b;
        }
    

Log in to reply
 

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