Leetcode

Solve the Equation

  • Time:O(n)
  • Space:O(n)

C++

class Solution {
 public:
  string solveEquation(string equation) {
    const string lhsEquation = equation.substr(0, equation.find('='));
    const string rhsEquation = equation.substr(equation.find('=') + 1);
    const auto& [lhsCoefficient, lhsConstant] = calculate(lhsEquation);
    const auto& [rhsCoefficient, rhsConstant] = calculate(rhsEquation);
    const int coefficient = lhsCoefficient - rhsCoefficient;
    const int constant = rhsConstant - lhsConstant;

    if (coefficient == 0 && constant == 0)
      return "Infinite solutions";
    if (coefficient == 0 && constant != 0)
      return "No solution";
    return "x=" + to_string(constant / coefficient);
  }

 private:
  pair<int, int> calculate(const string& s) {
    int coefficient = 0;
    int constant = 0;
    int num = 0;
    int sign = 1;

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (isdigit(c))
        num = num * 10 + (c - '0');
      else if (c == '+' || c == '-') {
        constant += sign * num;
        sign = c == '+' ? 1 : -1;
        num = 0;
      } else {
        if (i > 0 && num == 0 && s[i - 1] == '0')
          continue;
        coefficient += num == 0 ? sign : sign * num;
        num = 0;
      }
    }

    return {coefficient, constant + sign * num};
  }
};

JAVA

class Solution {
  public String solveEquation(String equation) {
    String[] equations = equation.split("=");
    int[] lhs = calculate(equations[0]);
    int[] rhs = calculate(equations[1]);
    int coefficient = lhs[0] - rhs[0];
    int constant = rhs[1] - lhs[1];

    if (coefficient == 0 && constant == 0)
      return "Infinite solutions";
    if (coefficient == 0 && constant != 0)
      return "No solution";
    return "x=" + constant / coefficient;
  }

  private int[] calculate(final String s) {
    int coefficient = 0;
    int constant = 0;
    int num = 0;
    int sign = 1;

    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (Character.isDigit(c))
        num = num * 10 + (c - '0');
      else if (c == '+' || c == '-') {
        constant += sign * num;
        sign = c == '+' ? 1 : -1;
        num = 0;
      } else {
        if (i > 0 && num == 0 && s.charAt(i - 1) == '0')
          continue;
        coefficient += num == 0 ? sign : sign * num;
        num = 0;
      }
    }

    return new int[] {coefficient, constant + sign * num};
  }
}

Python

class Solution:
  def solveEquation(self, equation: str) -> str:
    def calculate(s: str) -> tuple:
      coefficient = 0
      constant = 0
      num = 0
      sign = 1

      for i, c in enumerate(s):
        if c.isdigit():
          num = num * 10 + ord(c) - ord('0')
        elif c in '+-':
          constant += sign * num
          sign = 1 if c == '+' else -1
          num = 0
        else:
          if i > 0 and num == 0 and s[i - 1] == '0':
            continue
          coefficient += sign if num == 0 else sign * num
          num = 0

      return coefficient, constant + sign * num

    lhsEquation, rhsEquation = equation.split('=')
    lhsCoefficient, lhsConstant = calculate(lhsEquation)
    rhsCoefficient, rhsConstant = calculate(rhsEquation)
    coefficient = lhsCoefficient - rhsCoefficient
    constant = rhsConstant - lhsConstant

    if coefficient == 0 and constant == 0:
      return "Infinite solutions"
    if coefficient == 0 and constant != 0:
      return "No solution"
    return "x=" + str(constant // coefficient)