Python, Straightforward with Explanation


  • 1

    Evidently, we have 2 parts to our problem:

    • Break our string into separate tokens which represent one fraction each
    • Add the fractions together, keeping it in reduced form

    Let's decide how we want to break our string into tokens. Immediately after we see the second digit region, we know the first fraction must end there. To know whether we ended a digit region, we can look for a digit followed by a non-digit (or we are at the end of the string). Thus, every 2 digit regions, we'll report the token we've found. That token is something like "-10/3", which we'll convert into the integer tuple (-10, 3) representing fraction (-10 / 3).

    def fractionAddition(self, S):
        def iter_tokens(S):
            left = 0
            count = 0 
            for right, symbol in enumerate(S):
                if (right == len(S)-1 or 
                        symbol.isdigit() and not S[right + 1].isdigit()):
                    count += 1
                    if count % 2 == 0:
                        yield map(int, S[left: right+1].split('/'))
                        left = right + 1
    

    To add two fractions (a, b) and (c, d) together, we convert to a common denominator bd, so the fraction is (ad + bc, bd). To keep fraction (x, y) reduced, we should divide both the numerator and denominator by their greatest common divisor. We can finish as follows:

        def gcd(a, b):
            if a == 0: return b
            return gcd(b%a, a)
    
        def add((an, ad), (bn, bd)):
            n = an * bd + bn * ad
            d = ad * bd
            g = gcd(n, d)
            return n/g, d/g
    
        return "{}/{}".format(*reduce(add, iter_tokens(S)))
    

    We could have also leveraged the fractions library to simplify our calculation.

    def fractionAddition(self, S):
        from fractions import Fraction
        ans = Fraction(0, 1)
        left = count = 0
        for right, symbol in enumerate(S):
            if (right == len(S) - 1 or 
                    symbol.isdigit() and not S[right + 1].isdigit()):
                count ^= 1
                if not count:
                    ans += Fraction(*map(int, S[left: right+1].split('/')))
                    left = right + 1
        
        return "{}/{}".format(ans.numerator, ans.denominator)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.