Update fraction-to-recurring-decimal.py

kamyu104 · web-flow · commit b141c08af30d · 2016-07-18T21:39:25.000+08:00
diff --git a/Python/fraction-to-recurring-decimal.py b/Python/fraction-to-recurring-decimal.py
@@ -1,7 +1,8 @@
 # Time:  O(logn), where logn is the length of result strings
 # Space: O(1)
-#
-# Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
+
+# Given two integers representing the numerator and denominator of a fraction,
+# return the fraction in string format.
 # 
 # If the fractional part is repeating, enclose the repeating part in parentheses.
 # 
@@ -10,43 +11,38 @@
 # Given numerator = 1, denominator = 2, return "0.5".
 # Given numerator = 2, denominator = 1, return "2".
 # Given numerator = 2, denominator = 3, return "0.(6)".
-#
 
-class Solution:
-    # @return a string
+class Solution(object):
     def fractionToDecimal(self, numerator, denominator):
+        """
+        :type numerator: int
+        :type denominator: int
+        :rtype: str
+        """
         dvd, dvs = abs(numerator), abs(denominator)
-        integer, decimal, dict = "", "", {}
-        
-        if dvd > dvs:
-            integer = str(dvd / dvs)
-            dvd %= dvs
-        else:
-            integer = "0"
-        
+        result, lookup = "", {}
+        if (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0): 
+            result = "-"  
+        result += str(dvd / dvs)
+        dvd %= dvs
+
         if dvd > 0:
-            integer += "."
+            result += "."
         
-        idx = 0
-        while dvd:
-            if dvd in dict:
-                decimal = decimal[:dict[dvd]] + "(" + decimal[dict[dvd]:] + ")"
-                break
-            
-            dict[dvd] = idx
-            idx += 1
-            
+        while dvd and dvd not in lookup:
+            lookup[dvd] = len(result)
             dvd *= 10
-            decimal += str(dvd / dvs)
+            result += str(dvd / dvs)
             dvd %= dvs
-        
-        if (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0): 
-            return "-" + integer + decimal
-        else:
-            return integer + decimal
+
+        if dvd in lookup:
+            result = result[:lookup[dvd]] + "(" + result[lookup[dvd]:] + ")"
+
+        return result
+
 
 if __name__ == "__main__":
     print Solution().fractionToDecimal(1, 9)
     print Solution().fractionToDecimal(-50, 8)
     print Solution().fractionToDecimal(22, 2)
-    print Solution().fractionToDecimal(-22, -2)
+    print Solution().fractionToDecimal(-22, -2)
