Equal Rational Numbers

972. 相等的有理数

平均星级：4.43 (7次评分)

输入：s = "0.9(9)", t = "1." 输出：true 解释："0.9(9)" 代表 0.999999999... 永远重复，等于 1 。[有关说明，请参阅此链接] "1." 表示数字 1，其格式正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = "" 。

解决方案
- 方法一：分数类

解决方案

方法一：分数类

思路

因为给定的两个数字都表示一个分数，所以我们需要一个分数类去处理这两个分数。它应该能帮助我们将两个分数加起来，并且保证答案为最简形式。

算法

我们需要理解给定的两个分数，最困难的问题是如何表示它们。

比如说我们有一个字符串 S = "0.(12)"。它代表（定义 $r = \frac{1}{100}$ ）：

$S = \frac{12}{100} + \frac{12}{10000} + \frac{12}{10^6} + \frac{12}{10^8} + \frac{12}{10^10} + \cdots$

$S = 12 * (r + r^2 + r^3 + \cdots)$

$S = 12 * \frac{r}{1-r}$

其中 $(r + r^2 + r^3 + \cdots)$ 是一个等比数列求和问题。

总而言之，对于长度为 $k$ 的重复部分 $x$ ，会对答案有 $\frac{xr}{1-r}$ 的贡献，其中 $r = 10^{-k}$ 。

另外两部分就更容易计算了，因为它们仅仅是对数值的简单翻译。

复杂度分析

时间复杂度： $O(1)$ ，因为字符串 $S, T$ 的长度可以看作是 $O(1)$ 级别的。
空间复杂度： $O(1)$ 。