972.相等的有理数

相等的有理数

给定两个字符串表示的有理数，判断它们是否表示相同的数字。有理数格式：整数部分 + (非重复小数) + (重复小数部分用括号表示)。

示例 1:

输入：s = “0.(52)”, t = “0.5(25)”
输出：true

示例 2:

输入：s = “0.1666(6)”, t = “0.166(66)”
输出：true

提示:

• 字符串长度 <= 30
• 不包含前导零（除 “0” 外）

解析

将小数转换为分数形式，比较两个分数是否相等。

var isRationalEqual = function (s, t) {
  const parse = (str) => {
    let intPart = 0;
    let nonRep = 0;
    let nonRepLen = 0;
    let repLen = 0;

    let i = 0;
    while (i < str.length && str[i] !== '(') {
      if (str[i] !== '.') intPart = intPart * 10 + parseInt(str[i]);
      i++;
    }

    let nonRepStart = str.indexOf('.') + 1;
    let nonRepEnd = i;
    nonRepLen = nonRepEnd - nonRepStart;

    for (let j = nonRepStart; j < nonRepEnd; j++) {
      nonRep = nonRep * 10 + parseInt(str[j]);
    }

    let rep = 0;
    if (i < str.length) {
      i++;
      let repStart = i;
      let repEnd = str.indexOf(')', i);
      repLen = repEnd - repStart;
      for (let j = repStart; j < repEnd; j++) {
        rep = rep * 10 + parseInt(str[j]);
      }
    }

    const nonRepDivisor = Math.pow(10, nonRepLen);
    const repDivisor = Math.pow(10, repLen) - 1;

    let numerator = intPart * nonRepDivisor + nonRep;
    let denominator = nonRepDivisor;

    if (repLen > 0) {
      numerator = numerator * repDivisor + rep;
      denominator = denominator * repDivisor;
    }

    const g = gcd(numerator, denominator);
    return [numerator / g, denominator / g];
  };

  const sFrac = parse(s);
  const tFrac = parse(t);
  return sFrac[0] === tFrac[0] && sFrac[1] === tFrac[1];
};

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

时间复杂度 O(L)，空间复杂度 O(1)。