Easy to understand java solution using divide and conquer


  • 4
    S
    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
           if (input == null) {
               return new ArrayList<Integer>();
           }
           
           return helper(input, 0, input.length() - 1);
        }
        
        
        private List<Integer> helper(String input, int start, int end) {
            List<Integer> result = new ArrayList<Integer>();
            
            //if the currrent substring is a number, return
            try {
                    result.add(Integer.parseInt(input.substring(start, end + 1)));
                    return result;
            }
            //if not, do the parsing by the following
            catch (NumberFormatException e) {
                
            }
            
            for (int operatorIndex = start; operatorIndex <= end; operatorIndex++) {
                char currChar = input.charAt(operatorIndex);
                if (currChar == '+' || currChar == '-' || currChar == '*') {
                    //recursively compute all possible results from other sides of current operator
                    List<Integer> left = helper(input, start, operatorIndex - 1);
                    List<Integer> right = helper(input, operatorIndex + 1, end);
                    
                    //combine all possible results
                    for (int leftValue : left) {
                        for (int rightValue : right) {
                            int newValue;
                            char operator = input.charAt(operatorIndex);
                            if (operator == '+') {
                                newValue = leftValue + rightValue;
                            }
                            else if (operator == '-') {
                                newValue = leftValue - rightValue;
                            }
                            else {
                                newValue = leftValue * rightValue;
                            }
                            result.add(newValue);
                        }
                    }
                }
            }
            return result;
            
        }
    }

  • 0
    Y

    how do you handle cases where a number is more than one digit?


Log in to reply
 

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