592: Space 98%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Split the expression string into individual fractions using the re.fin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Split the expression string into individual fractions using the re.findall function and regular expression pattern [+-]?\\d+/\\d+. This will match any fraction in the expression, including negative fractions and fractions with whole numbers.\n2. Convert the list of fraction strings to a list of tuples (numerator, denominator) by splitting each fraction string at the \'/\' character and converting the resulting strings to integers using map.\n3. Find the least common multiple (LCM) of the denominators of all the fractions. To do this, initialize lcm to 1 and loop through each fraction, multiplying lcm by the fraction\'s denominator divided by the greatest common divisor of lcm and the fraction\'s denominator.\n4. Add the numerators of all the fractions, after multiplying each numerator by a factor so that the fractions all have a common denominator equal to the lcm found in step 3.\n5. Simplify the resulting fraction by dividing the numerator and denominator by their greatest common divisor using the math.gcd function.\n6. Return the simplified fraction as a string in the format numerator/denominator.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def fractionAddition(self, expression: str) -> str:\n        # Split the expression into individual fractions\n        fractions = re.findall(\'[+-]?\\d+/\\d+\', expression)\n        \n        # Convert the fractions to a list of tuples (numerator, denominator)\n        fractions = [tuple(map(int, fraction.split(\'/\'))) for fraction in fractions]\n        \n        # Find the LCM of the denominators\n        lcm = 1\n        for fraction in fractions:\n            lcm = lcm * fraction[1] // math.gcd(lcm, fraction[1])\n        \n        # Add the numerators after multiplying by the appropriate factor\n        numerator_sum = sum([fraction[0] * (lcm // fraction[1]) for fraction in fractions])\n        \n        # Simplify the fraction\n        gcd = math.gcd(numerator_sum, lcm)\n        numerator = numerator_sum // gcd\n        denominator = lcm // gcd\n        \n        # Return the simplified fraction as a string\n        return str(numerator) + \'/\' + str(denominator)\n\n```
['Math', 'String', 'Simulation', 'Python', 'Python3']