Bottom up dp AC solution


  • 1
    A
      public List<Integer> diffWaysToCompute(String input) {
        List<String> tokens = tokenize(input);
        int size = tokens.size() / 2;
        List<List<List<Integer>>> result = new ArrayList<>();
        // init
        for(int i = 0; i < input.length(); i++)
          result.add(new ArrayList<List<Integer>>(size));
    
        for(int row = 0; row <= size; row++){
          for(int col = 0; col <= size; col++){
            result.get(row).add(new ArrayList<Integer>());
          }
        }
    
        for(int row = size; row >= 0; row--){
          for(int col = row; col <= size; col++){
            if(col == row)
              result.get(row).get(col).add(Integer.parseInt(tokens.get(row*2)));
            else{
              for(int split = col - 1; split >= 0; split--){
                List<Integer> tmp = cross_result(tokens.get(split*2+1), result.get(row).get(split), result.get(split+1).get(col));
                result.get(row).get(col).addAll(tmp);
              }
            }
          }
        }
        return result.get(0).get(size);      
      }
      
      // Given two lists and an operator, we apply operator on each pair from l1 and l2
      private List<Integer> cross_result(String op, List<Integer> l1, List<Integer> l2){
        List<Integer> result = new ArrayList<>();
        for(int i1 : l1){
          for(int i2 : l2)
            result.add(compute(op, i1, i2));
        }
        return result;
      }
    
      private int compute(String op, int arg1, int arg2){
        int val = 0;
        if(op.equals("+")) val = arg1 + arg2;
        else if(op.equals("-")) val = arg1 - arg2;
        else val = arg1 * arg2;
        return val;
      }
      
      // Convert expression to a list of tokens, each token is either a number or an operator
      private List<String> tokenize(String input){
        List<String> list = new ArrayList<>();
        int start = 0, end = 0;
        while(end < input.length()){
          char cur = input.charAt(end);
          if(is_char(cur)){
            list.add(input.substring(start, end));
            list.add(input.substring(end, end+1));
            start = end + 1;
            end = start;
          }else{
            end++;
          }
        }
        list.add(input.substring(start, end));
        return list;
      }
    
      private boolean is_char(char c){
        return c == '+' || c == '-' || c == '*';
      }

Log in to reply
 

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