Equal Rational Numbers Python Solution

LeetCode 972, Hard. Topics: Math, String. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 972   # by problem number
lcpy gen -s equal_rational_numbers   # by problem name

Problem

Given two strings s and t, each of which represents a non-negative rational number, return true if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number. A rational number can be represented using up to three parts: <IntegerPart>, <NonRepeatingPart>, and a <RepeatingPart>. The number will be represented in one of the following three ways:

<IntegerPart>
- For example, 12, 0, and 123.
<IntegerPart>.<NonRepeatingPart>
- For example, 0.5, 1., 2.12, and 123.0001.
<IntegerPart>.<NonRepeatingPart>(<RepeatingPart>)
- For example, 0.1(6), 1.(9), and 123.00(1212).

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Examples

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Input: s = "0.1666(6)", t = "0.166(66)"
Output: true

Input: s = "0.9(9)", t = "1."
Output: true
Explanation: "0.9(9)" represents 0.999999999... repeated forever, which equals 1.
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Constraints

Each part consists only of digits.
The <IntegerPart> does not have leading zeros (except for the zero itself).
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from fractions import Fraction


class Solution:
    # Time: O(len(s) + len(t))
    # Space: O(1)
    def is_rational_equal(self, s: str, t: str) -> bool:
        return self._to_fraction(s) == self._to_fraction(t)

    def _to_fraction(self, s: str) -> Fraction:
        base, repeating = s.split("(", 1) if "(" in s else (s, "")
        repeating = repeating.rstrip(")")
        integer_part, non_repeating = base.split(".", 1) if "." in base else (base, "")
        value = Fraction(int(integer_part))
        if non_repeating:
            value += Fraction(int(non_repeating), 10 ** len(non_repeating))
        if repeating:
            scale = 10 ** len(non_repeating)
            value += Fraction(int(repeating), scale * (10 ** len(repeating) - 1))
        return value

Complexity

Time	Space
O(len(s) + len(t))	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Equal Rational Numbers Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags