Question

640. Solve the Equation

中文文档

Description

Solve a given equation and return the value of 'x' in the form of a string "x=#value". The equation contains only '+', '-' operation, the variable 'x' and its coefficient. You should return "No solution" if there is no solution for the equation, or "Infinite solutions" if there are infinite solutions for the equation.

If there is exactly one solution for the equation, we ensure that the value of 'x' is an integer.

 

Example 1:

Input: equation = "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: equation = "x=x"
Output: "Infinite solutions"

Example 3:

Input: equation = "2x=x"
Output: "x=0"

 

Constraints:

• 3 <= equation.length <= 1000
• equation has exactly one '='.
• equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.

Solutions

Solution 1

class Solution:
  def solveEquation(self, equation: str) -> str:
    def f(s):
      x = y = 0
      if s[0] != '-':
        s = '+' + s
      i, n = 0, len(s)
      while i < n:
        sign = 1 if s[i] == '+' else -1
        i += 1
        j = i
        while j < n and s[j] not in '+-':
          j += 1
        v = s[i:j]
        if v[-1] == 'x':
          x += sign * (int(v[:-1]) if len(v) > 1 else 1)
        else:
          y += sign * int(v)
        i = j
      return x, y

    a, b = equation.split('=')
    x1, y1 = f(a)
    x2, y2 = f(b)
    if x1 == x2:
      return 'Infinite solutions' if y1 == y2 else 'No solution'
    return f'x={(y2 - y1) // (x1 - x2)}'

class Solution {
  public String solveEquation(String equation) {
    String[] es = equation.split("=");
    int[] a = f(es[0]), b = f(es[1]);
    int x1 = a[0], y1 = a[1];
    int x2 = b[0], y2 = b[1];
    if (x1 == x2) {
      return y1 == y2 ? "Infinite solutions" : "No solution";
    }
    return "x=" + (y2 - y1) / (x1 - x2);
  }

  private int[] f(String s) {
    int x = 0, y = 0;
    if (s.charAt(0) != '-') {
      s = "+" + s;
    }
    int i = 0, n = s.length();
    while (i < n) {
      int sign = s.charAt(i) == '+' ? 1 : -1;
      ++i;
      int j = i;
      while (j < n && s.charAt(j) != '+' && s.charAt(j) != '-') {
        ++j;
      }
      String v = s.substring(i, j);
      if (s.charAt(j - 1) == 'x') {
        x += sign * (v.length() > 1 ? Integer.parseInt(v.substring(0, v.length() - 1)) : 1);
      } else {
        y += sign * Integer.parseInt(v);
      }
      i = j;
    }
    return new int[] {x, y};
  }
}

func solveEquation(equation string) string {
  f := func(s string) []int {
    x, y := 0, 0
    if s[0] != '-' {
      s = "+" + s
    }
    i, n := 0, len(s)
    for i < n {
      sign := 1
      if s[i] == '-' {
        sign = -1
      }
      i++
      j := i
      for j < n && s[j] != '+' && s[j] != '-' {
        j++
      }
      v := s[i:j]
      if s[j-1] == 'x' {
        a := 1
        if len(v) > 1 {
          a, _ = strconv.Atoi(v[:len(v)-1])
        }
        x += sign * a
      } else {
        a, _ := strconv.Atoi(v)
        y += sign * a
      }
      i = j
    }
    return []int{x, y}
  }

  es := strings.Split(equation, "=")
  a, b := f(es[0]), f(es[1])
  x1, y1 := a[0], a[1]
  x2, y2 := b[0], b[1]
  if x1 == x2 {
    if y1 == y2 {
      return "Infinite solutions"
    } else {
      return "No solution"
    }
  }
  return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}

function solveEquation(equation: string): string {
  const [left, right] = equation.split('=');
  const createExpr = (s: string) => {
    let x = 0;
    let n = 0;
    let i = 0;
    let sym = 1;
    let cur = 0;
    let isX = false;
    for (const c of s) {
      if (c === '+' || c === '-') {
        if (isX) {
          if (i === 0 && cur === 0) {
            cur = 1;
          }
          x += cur * sym;
        } else {
          n += cur * sym;
        }
        isX = false;
        cur = 0;
        i = 0;
        if (c === '+') {
          sym = 1;
        } else {
          sym = -1;
        }
      } else if (c === 'x') {
        isX = true;
      } else {
        i++;
        cur *= 10;
        cur += Number(c);
      }
    }
    if (isX) {
      if (i === 0 && cur === 0) {
        cur = 1;
      }
      x += cur * sym;
    } else {
      n += cur * sym;
    }
    return [x, n];
  };
  const lExpr = createExpr(left);
  const rExpr = createExpr(right);
  if (lExpr[0] === rExpr[0]) {
    if (lExpr[1] !== rExpr[1]) {
      return 'No solution';
    }
    return 'Infinite solutions';
  }
  return `x=${(lExpr[1] - rExpr[1]) / (rExpr[0] - lExpr[0])}`;
}