ตรวจสอบจำนวนมีมีค่าเท่ากันใน C++

คำอธิบายปัญหา

ให้สตริง S และ T แทนจำนวนตรรกยะ (rational number) อาจมีวงเล็บเพื่อบ่งบอกส่วนที่ซ้ำ ตรวจสอบว่าแทนจำนวนเดียวกันหรือไม่

รูปแบบที่เป็นไปได้:

• Integer only: "123"
• Integer.NonRepeating: "0.5", "2.12"
• Integer.NonRepeating(Repeating): "0.1(6)", "0.9(9)"

ตัวอย่าง

S = "0.(52)", T = "0.5(25)" → Output: true (ทั้งคู่ = 52/99)

แนวทางแก้ปัญหา: แปลงเป็นทศนิยมยาวพอ

1. หาตำแหน่ง '(' ในสตริง
2. ถ้ามี: แยก base (ส่วนก่อนวงเล็บ) และ rep (ส่วนในวงเล็บ)
3. ขยาย base โดยต่อ rep ซ้ำ 20 ครั้ง (พอสำหรับ precision double)
4. แปลงเป็น double ด้วย stod()
5. เปรียบเทียบค่า double ของทั้งสองสตริง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    double f(string S) {
        auto i = S.find('(');
        if(i != string::npos) {
            string base = S.substr(0, i);
            string rep = S.substr(i+1, S.length()-i-2);
            for(int j=0; j<20; j++) base += rep;
            return stod(base);
        }
        return stod(S);
    }
    
public:
    bool isRationalEqual(string S, string T) {
        return f(S) == f(T);
    }
};

หมายเหตุ

• วิธีนี้ใช้ double precision ซึ่งพอสำหรับกรณีทั่วไปแต่อาจมีปัญหา precision กรณีขอบ
• วิธีที่แม่นยำกว่า: แปลงเป็นเศษส่วน (numerator/denominator) โดยใช้สูตรคณิตศาสตร์

ความซับซ้อน

• เวลา: O(|S| + |T|)
• พื้นที่: O(|S| + |T|)