Approach #1: Polynomial Class [Accepted]

Intuition

Keep a class Poly that knows a map from a list of free variables to a coefficient, and support operations on this class.

Algorithm

Each function is straightforward individually. Let's list the functions we use:

  • Poly:add(this, that) returns the result of this + that.
  • Poly:sub(this, that) returns the result of this - that.
  • Poly:mul(this, that) returns the result of this * that.
  • Poly:evaluate(this, evalmap) returns the polynomial after replacing all free variables with constants as specified by evalmap.
  • Poly:toList(this) returns the polynomial in the correct output format.

  • Solution::combine(left, right, symbol) returns the result of applying the binary operator represented by symbol to left and right.

  • Solution::make(expr) makes a new Poly represented by either the constant or free variable specified by expr.
  • Solution::parse(expr) parses an expression into a new Poly.

Complexity Analysis

  • Time Complexity: Let is the length of expression and is the length of evalvars and evalints. With an expression like (a + b) * (c + d) * (e + f) * ... the complexity is .

  • Space Complexity: .


Analysis written by: @awice.