Equal rational numbers

Math String

45.9% acceptance

Feb 25, 2026

106

218

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: , , and a . The number will be represented in one of the following three ways: For example, 12, 0, and 123. <.> For example, 0.5, 1., 2.12, and 123.0001. <.><(><)> For example, 0.1(6), 1.(9), 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).

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_rational_equal(s: String, t: String) -> bool {
    fn to_frac(s: &str) -> (i64, i64) {
      // Parse and return numerator, denominator
      // Format: integer.nonrep(rep) or integer.nonrep or integer
      if let Some(dot_pos) = s.find('.') {
        let int_part: i64 = s[..dot_pos].parse().unwrap();
        let after_dot = &s[dot_pos+1..];
        if let Some(paren_pos) = after_dot.find('(') {
          let non_rep = &after_dot[..paren_pos];
          let rep = &after_dot[paren_pos+1..after_dot.len()-1];
          // Value = int + non_rep/10^nr_len + rep/(10^nr_len * (10^r_len - 1))
          let nr_len = non_rep.len() as u32;
          let r_len = rep.len() as u32;
          let pow_nr = 10i64.pow(nr_len);
          let pow_r = 10i64.pow(r_len);
          let non_rep_n: i64 = if non_rep.is_empty() { 0 } else { non_rep.parse().unwrap() };
          let rep_n: i64 = if rep.is_empty() { 0 } else { rep.parse().unwrap() };
          // Combined fraction:
          // num = int * pow_nr * (pow_r - 1) + non_rep_n * (pow_r - 1) + rep_n
          // den = pow_nr * (pow_r - 1)
          let den = pow_nr * (pow_r - 1);
          let num = int_part * den + non_rep_n * (pow_r - 1) + rep_n;
          let g = gcd(num.abs(), den.abs());
          (num / g, den / g)
        } else {
          // Just decimal: int.nonrep
          let nr_len = after_dot.len() as u32;
          let pow_nr = 10i64.pow(nr_len);
          let nr_n: i64 = if after_dot.is_empty() { 0 } else { after_dot.parse().unwrap() };
          let num = int_part * pow_nr + nr_n;
          let den = pow_nr;
          let g = gcd(num.abs(), den.abs());
          (num / g, den / g)
        }
      } else {
        let n: i64 = s.parse().unwrap();
        (n, 1)
      }
    }
    fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a } else { gcd(b, a % b) } }
    to_frac(&s) == to_frac(&t)
  }
}