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.
In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:
<IntegerPart>(e.g. 0, 12, 123)<IntegerPart><.><NonRepeatingPart>(e.g. 0.5, 1., 2.12, 2.0001)<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>(e.g. 0.1(6), 0.9(9), 0.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)
Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.
Example 1:
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.
Example 2:
Input: S = "0.1666(6)", T = "0.166(66)" Output: true
Example 3:
Input: S = "0.9(9)", T = "1." Output: true Explanation: "0.9(9)" represents 0.999999999... repeated forever, which equals 1. [See this link for an explanation.] "1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".
Note:
- Each part consists only of digits.
- The
<IntegerPart>will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.) 1 <= <IntegerPart>.length <= 40 <= <NonRepeatingPart>.length <= 41 <= <RepeatingPart>.length <= 4
Solution1: Expend the string
Extend the string to 16+ more digits and covert it to double.
0.9(9) => 0.99999999999999
0.(52) => 0.525252525252525
0.5(25) => 0.5252525252525
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, running time: 4 ms class Solution { public: bool isRationalEqual(string S, string T) { auto convert = [](string s) { // 0.1234(567) // 01234567890 // i = 1, p = 6 auto i = s.find('.'); auto p = s.find('('); if (p != string::npos) { string r = s.substr(p + 1, s.length() - p - 2); s = s.substr(0, p); while (s.length() < 16) s += r; } return stod(s); }; return abs(convert(S) - convert(T)) < 1e-10; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def isRationalEqual(self, S, T): def convert(s): i = s.find('.') p = s.find('(') if p >= 0: r = s[p+1:-1] s = s[0:p] while len(s) < 16: s += r return float(s) return abs(convert(S) - convert(T)) < 1e-10 |
Solution 2: Convert to a friction number
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// Author: Huahua, running time: 24 ms. class Friction { public: Friction(long n = 0, long d = 1) { long g = __gcd(n, d); n_ = n / g; d_ = d / g; } Friction operator+(const Friction& o) const { return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_); } bool operator==(const Friction& o) const { return this->n_ * o.d_ == this->d_ * o.n_; } private: long n_; long d_; }; class Solution { public: bool isRationalEqual(string S, string T) { auto convert = [](string s) { std::regex re("(\\d+)\\.?(\\d+)?(\\((\\d+)\\))?"); std::smatch matches; std::regex_match(s, matches, re); string int_part = matches[1].str(); string nr_part = matches[2].str(); string r_part = matches[4].str(); Friction f(stoi(int_part), 1); const int base = pow(10, nr_part.length()); if (nr_part.length()) f = f + Friction(stoi(nr_part), base); if (r_part.length()) f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1) * base); return f; }; return convert(S) == convert(T); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment