[Leetcode]640. Solve the Equation

Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.

To solve a linear equation of single variable:

  • We need to find the coefficient of the x and the constant value.
  • We would treat the coefficient and the constant differently if they appear on different sides of =, as we need to flip the sign. Therefore, we need a helper function to parse both the left and right parts.
  • In the helper, we need to deal with three cases:
    • equation[i] is a number
    • equation[i] is the x
    • equation[i] is +/-
class Solution:
    def solveEquation(self, equation: str) -> str:
        def helper(l,r): # left inclusive and right exclusive
            constant = unknown = 0
            sign,val = 1,''
            while l < r:
                if equation[l].isnumeric():
                    val += equation[l]
                elif equation[l] == 'x':
                    unknown += sign*int(val or '1') # in case the coefficient is 1
                    val = ''
                else: # meet a +/-
                    if val:
                        constant += sign*int(val)
                    sign = 1 if equation[l]=='+' else -1
                    val = ''
                l += 1
            if val: # if the last digit is a number
                constant += sign*i
            return constant,unknown
    
        mid = equation.find('=')
        constant1,unknown1 = helper(0,mid)
        constant2,unknown2 = helper(mid+1,len(equation))
        const,var = constant2-constant1,unknown1-unknown2
        # print(a,b)
        if var == 0:
            if const == 0: return "Infinite solutions"
            else: return "No solution"
        else: return 'x={}'.format(const//var)

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments