# 640. Solve the Equation     • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 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 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}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public String solveEquation(String equation) { String[] equations = equation.split("="); int[] lhs = calculate(equations); int[] rhs = calculate(equations); int coefficient = lhs - rhs; int constant = rhs - lhs; 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}; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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)